【AtCoder2304】Cleaning

The question

A tree has n Nodes , node i Yes A[i] A stone . Remove all stones .
For each stone removal operation , Select two leaf nodes (u,v)(u Can not be equal to v), remove u To v A stone for each node on the path ( Include u,v). Be careful : If there is a node on this path without stones , The operation cannot be performed .
（ The degree of leaf node here is 1 The node of ）
Can the stones on the tree be removed through the above operations .

Answer key

Find a degree greater than 1 Node of is root ,dfs down , Every time I go back , How many more operations are needed on this tree .
The current node is u, processed u Of all the sons of , There are still some operations left over from these subtrees , Need to pass through u To complete .
The remaining operands are paired in pairs , That is, it forms several paths , Finally, make the remaining operands of the subtree and the current node u The number of stones is the same , The remaining stones need to be removed by a higher path .

Let the son subtree remain sum operations , When pairing , Take two operations from the son subtree each time , Remove a stone from the current node , Then the total number of operations is sum-A[u].
sum<A[u] unsolvable （ The number of operations is negative ）
A[u]<sum-A[u] unsolvable （ There are not enough stones at the current node ）
take mx Is the maximum value of the remaining operands of the son subtree
sum-mx<sum-A[u] unsolvable （ Cannot pair in pairs ）

For the root node , The remaining operands need to be 0, Then we must satisfy A[u]==sum/2

If n==2, Special judgement （ Root not found ...）

Code

#include<cstdio> #include<cstdlib> #include<vector> #include<algorithm> using namespace std; const int MAXN=100005; void NoSolution() {
      puts("NO"); fclose(stdin); fclose(stdout); exit(0); } int n,A[MAXN]; vector<int> adj[MAXN]; int dfs(int u,int fa=0) {
      if(adj[u].size()==1U) return A[u]; long long sum=0; int tmp=0,mx=0; for(int i=0;i<(int)adj[u].size();i++) {
      int v=adj[u][i]; if(v==fa) continue; tmp=dfs(v,u); mx=max(mx,tmp); sum+=tmp; } if(fa==0) {
      if(sum%2==1||mx>sum/2||A[u]!=sum/2) NoSolution(); return 0; } long long delta=sum-A[u]; if(A[u]<delta||sum<A[u]||sum-mx<delta) NoSolution(); return A[u]-delta; } int main() {
      scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&A[i]); if(n==2) {
      if(A[1]==A[2]) puts("YES"); else puts("NO"); return 0; } for(int i=1;i<n;i++) {
      int a,b; scanf("%d%d",&a,&b); adj[a].push_back(b); adj[b].push_back(a); } for(int i=1;i<=n;i++) if(adj[i].size()>1U) {
      dfs(i); break; } puts("YES"); return 0; }