Codeforces348B Apple Tree DFS

炒沙作縻终不饱，缕冰文章费工巧。这篇文章主要讲述Codeforces348B Apple Tree DFS相关的知识，希望能为你提供帮助。
题意：一颗苹果树上每个叶子结点苹果个数不同，现在需要从苹果树上取下最少的苹果，使得对于每一个结点，他的所有子树的苹果个数相同。
两遍dfs。
对于两颗子树，如果第一颗子树有四个结点，第二棵子树有五棵结点，又因为第一棵子树的权值等于第二棵子树的权值，所以说，两颗树的权值一定是 4 的倍数且是5的倍数，所以每棵子树都是20的倍数。深入理解一下这个意思，我们可以得到这样的结论，对于第一棵树，它转化为20个兄弟，并排着，第二棵树可以变成20个兄弟并排着，那么对于这两棵树的父亲可以变成40个结点并排。然后，来想一下，第一棵树的四个儿子，显然，每个儿子必然是5的倍数，所以每个儿子可以变成五份，这和第一个结点变成20份等价。
现在解决这棵子树能分成多少份，下面就来解决，每个份最大是多少，显然，对于每个叶子结点 L = min（L，叶子结点权值V / 叶子结点应该被分成NUM份）

文章图片

1 #include < iostream> 2 #include < vector> 3 #include < cstdio> 4 #include < cstdlib> 5 using namespace std; 6 long long a[1111111]; 7 long long s[1111111]; 8 long long S; 9 long long L = 1e15; 10 long long ans = 0; 11int N; 12 vector< int> E[1111111]; 13 long long gcd(long long x,long long y) 14 { 15return y==0?x:gcd(y,x%y); 16 } 17 long long lca(long long x,longlong y) 18 { 19return x*(y/gcd(x,y)); 20 } 21 long long dfs(int u,int p) 22 { 23if (E[u].size()==1& & u!=1) 24{ 25s[u] = a[u]; 26return 1LL; 27} 28long long num = 1; 29for (int i =0 ; i< E[u].size(); i++) 30{ 31if (E[u][i]==p) continue; 32num = lca(num,dfs(E[u][i],u)); 33s[u] += s[E[u][i]]; 34} 35if ((E[u].size()-(u==1?0:1))*num > = S) {cout < < S < < endl; exit(0); } 36return (E[u].size()-(u==1?0:1))*num; 37 } 38 void dfs2(int u,int p,long long num) 39 { 40if (E[u].size()==1& & u!=1) 41{ 42L = min(L,s[u]/num); 43} 44for (int i =0 ; i< E[u].size(); i++) 45{ 46if (E[u][i]==p) continue; 47dfs2(E[u][i],u,num/(E[u].size()-(u==1?0:1))); 48} 49 } 50 int main() 51 { 52 53//freopen("in.txt","r",stdin); 54cin > > N; 55for (int i = 1; i< =N; i++) 56{ 57scanf("%I64d",& a[i]); 58S+=a[i]; 59} 60for (int i = 1; i< N ; i++) 61{ 62int x,y; 63scanf("%d%d",& x,& y); 64E[x].push_back(y); 65E[y].push_back(x); 66} 67long long dd = dfs(1,0); 68dfs2(1,0,dd); 69if (dd * L > = S) 70{ 71cout < < 0< < endl; 72} 73else 74{ 75cout < < S-dd*L< < endl; 76} 77return 0; 78 }

View Code【Codeforces348B Apple Tree DFS】