网站管理员功能,做今网站,深圳华控赛格公司官网,上海最新新闻今天problem
洛谷链接
solution
显然#xff0c;颜色相同的灯泡形成一个连通块#xff0c;且连通块的大小 i∣ni\mid ni∣n。
这道题要能发现一个结论#xff1a;一定至少存在一种颜色的连通块 满足该联通块内的任意一个节点 都不是异种颜色点 的父亲。
即#xff0c;至少…problem
洛谷链接
solution
显然颜色相同的灯泡形成一个连通块且连通块的大小 i∣ni\mid ni∣n。
这道题要能发现一个结论一定至少存在一种颜色的连通块 满足该联通块内的任意一个节点 都不是异种颜色点 的父亲。
即至少有一个点其子树(含自己)内中所有点颜色均相同。
证明的话可以考虑将每种颜色连通块看作一个点。
父亲与儿子颜色不同的边转化到新图上的父亲颜色连通块点到儿子颜色联通块点的一条有向边。
显然这是一个 DAG\text{DAG}DAG得证。如果成环意味着原图上某个颜色点就没有形成一个连通块而是多个
拓扑排序传递连通块大小我们可以推出每个连通块内都至少有个点 uuu 满足 i∣sizui\mid siz_ui∣sizu。
那么就可以做了本题特殊的性质满足每个点的父亲编号都小于自己直接倒序遍历统计子树大小即可。
枚举联通块大小 iii枚举所有 i∣ji\mid ji∣j 记录 sizujsiz_ujsizuj 的点有 cntjcnt_jcntj 个将这些节点数累和 tottottot。
最后看 tot∗i≥ntot*i\ge ntot∗i≥n 是否包含了整棵树。
code
#include bits/stdc.h
using namespace std;
#define maxn 1200005
int n;
int f[maxn], siz[maxn], cnt[maxn];void read( int x ) {x 0; char s getchar();while( s 0 or s 9 ) s getchar();while( 0 s and s 9 ) {x ( x 1 ) ( x 3 ) ( s ^ 48 );s getchar();}
}int main() {scanf( %d, n );for( int i 2;i n;i ) read( f[i] );for( int t 1;t 10;t ) {printf( Case #%d:\n, t );if( t ^ 1 ) {for( int i 2;i n;i )f[i] ( f[i] 19940105 ) % ( i - 1 ) 1;}for( int i 1;i n;i ) siz[i] 1, cnt[i] 0;for( int i n;i;i -- ) siz[f[i]] siz[i];//siz[i]:i子树的大小 含自己for( int i 1;i n;i ) cnt[siz[i]] ;//cnt[i]:子树大小为i的节点个数for( int i 1;i n;i ) //枚举连通块大小if( n % i 0 ) {int tot 0;for( int j 1;j * i n;j ) { //加上所有子树大小为i倍数的节点个数tot cnt[i * j];if( tot * i n ) {//一个节点至少含i个点 判断是否包含了整棵树printf( %d\n, i );break;}}}}return 0;
}
