Codeforces Round 1107 (Div. 3)DE
D
思路：肯定是一个一个操作或者两个两个操作最优，对于a[i]<b[i]的这种情况很好办直接加就行，难点在于a[i]>b[i]的这种情况，这种情况不好办，那么a[i]<b[i]可以看成这个点的价值，可以对右边产生贡献例如：
1 3 4
5 3 1
我可以先：
1 0 4
2 0 4
再：
1 3 4
2 3 4
最后给1加上1就行了，
所以这个a[i]<b[i]这个差值是可以向右一直移动的，
为了模拟，我们令now初始=0，遇到a[i]<b[i]则+1，遇到a[i]>b[i]就减少，如果不够这个减就说明方案不可行输出no
代码：
void solve(){ int n;cin>>n; vector<int>a(n+10),b(n+10); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; int now=0; for(int i=1;i<=n;i++){ if(a[i]<=b[i]){ now+=b[i]-a[i]; } else{ if(now<a[i]-b[i]){ cout<<"NO"<<endl; return; } now-=(a[i]-b[i]); } } cout<<"YES"<<endl; }E
思路：
u v w观察样例发现，中间的节点要被乘三次，所以中间节点是完全平方数，对中间节点进行操作，可知，有两种贡献方式，一种是中间节点是u,v,w其中一个，一种是不是，对应了选2还是3个“儿子”：
选两个：
int s2=0; int k=son.size()-1; vector<int>cnt2(k+10); for(int i=1;i<=k;i++){ cnt2[i]=son[i]*(s-son[i]); s2+=cnt2[i]; } s2/=2;选三个：
int s3=0; for(int i=1;i<=k;i++){ s3+=son[i]*(s2-cnt2[i]); } s3/=3; ans+=s2+s3;代码：
void solve(){ int n;cin>>n; vector<int>a(n+10); for(int i=1;i<=n;i++) cin>>a[i]; vector<vector<int> >g(n+10); for(int i=1;i<=n-1;i++){ int u,v;cin>>u>>v; g[u].push_back(v),g[v].push_back(u); } vector<int>cnt(n+10,1); auto dfs=[&](auto &&dfs,int u,int fa)->void{ for(auto v:g[u]){ if(v==fa) continue; dfs(dfs,v,u); cnt[u]+=cnt[v]; } };dfs(dfs,1,-1); vector<int>pre(n+10); int ans=0; auto dfs2=[&](auto &&dfs2,int u,int fa)->void{ vector<int>son(1); int s=0; son.push_back(pre[u]);s+=pre[u]; for(auto v:g[u]){ if(v==fa) continue; pre[v]=pre[u]+cnt[u]-cnt[v]; dfs2(dfs2,v,u); son.push_back(cnt[v]); s+=cnt[v]; } int sq=sqrt(a[u]); if(sq*sq==a[u]){ int s2=0; int k=son.size()-1; vector<int>cnt2(k+10); for(int i=1;i<=k;i++){ cnt2[i]=son[i]*(s-son[i]); s2+=cnt2[i]; } s2/=2; int s3=0; for(int i=1;i<=k;i++){ s3+=son[i]*(s2-cnt2[i]); } s3/=3; ans+=s2+s3; } };dfs2(dfs2,1,-1); cout<<ans<<endl; }