Justiﬁed Jungle

Problem J: Justiﬁed Jungle

Time limit: 6 s Memory l

imit: 512 MiB

As you probably know, a tree is a graph consisting of n nodes and n−1 undirected edges in which any two nodes are connected by exactly one path. A forest is a graph consisting of one or more trees. In other words, a graph is a forest if every connected component is a tree. A forest is justiﬁed if all connected components have the same number of nodes. Given a tree G consisting of n nodes, ﬁnd all positive integers k such that a justiﬁed forest can be obtained by erasing exactly k edges from G. Note that erasing an edge never erases any nodes. In particular when we erase all n−1 edges from G, we obtain a justiﬁed forest consisting of n one-node components.
Input The ﬁrst line contains an integer n (2≤ n ≤1000000) — the number of nodes in G. The k-th of the following n−1 lines contains two different integers ak and bk (1≤ ak,bk ≤n) — the endpoints of the k-th edge.
Output
The ﬁrst line should contain all wanted integers k, in increasing order.
Example
input
8 1 2 2 3 1 4 4 5 6 7 8 3 7 3
output
1 3 7
Figures depict justiﬁed forests obtained by erasing 1, 3 and 7 edges from the tree in the example input.

 // 题目大意：删去k条边，树变为相等个点的连通分量，求所有正整数k。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define maxn 1000006

 int head[maxn],cnt,siz[maxn],v[maxn],n;

 struct edge{

     int to,nxt;

 }e[maxn<<];

 void add_edge(int u,int v){

     e[cnt].to=v;

     e[cnt].nxt=head[u];

     head[u]=cnt++;

 }

 void dfs(int u,int fa){

     siz[u]=;

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].to;

         if(v==fa) continue;

         dfs(v,u);

         siz[u]+=siz[v];

     }

     v[siz[u]]++;

 }

 bool check(int x){

     x++;

     if(n%x) return ;

     int w=n/x,sum=;

     for(int i=w;i<=n;i+=w) sum+=v[i];

     return sum==x;

 }

 int main(){

     memset(head,-,sizeof head);

     scanf("%d",&n);

     for(int i=;i<n-;i++){

         int a,b;

         scanf("%d%d",&a,&b);

         add_edge(a,b);

         add_edge(b,a);

     }

     dfs(,-);

     for(int i=;i<=n;i++){

         if(check(i)) printf("%d ",i);

     }

     return ;

 }

巴特西

Justiﬁed Jungle

最新文章

热门文章