题：https://ac.nowcoder.com/acm/contest/5278/G
题意：给定n个点的树，每个节点有权值，每个节点的权值每时刻都会向上移动一个高度，当节点的权值大于1时，这个节点就会在此节点上权值减少一，直至移动到树根，把最后的权值加到答案里去，最后问这个答案总和是多少？
分析：我们知道，不同高度在向根跑的过程中权值的合并（路径合并），权值减少的过程是互不影响的，这就提示我们可以把同一高度的节点划分开来，下面对于同一高度的一组来分析；
其中最复杂的情况就是路径的合并，每条路径的合并肯定就是在俩俩的lca合并或是俩俩的lca的lca合并或。。。，我们就想办法把这一组的lca全部求出来呢？因为求出来后，我们就直接模拟答案就行了；
而有一个结论就是，同一高度的节点的全部lca，就是以各个节点dfs序为序，排序后相邻的节点的lca就是这些节点向跟跑会经过的结合点，从这可以看出，所有结合点不会超过这一高度节点数-1；
在处理的时候，我们只需对非0点进行处理，对于俩个相邻节点x，y到lca中去，中间不会有结合，那么x到lca的贡献就是他当前的权值-（x到lca的深度之差），y也同理
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int M=2e5+5; vector<int>g[M]; int sz[M],deep[M],dfn[M],cnt,f[M],tp[M],son[M],id[M],fa[M]; ll a[M],val[M]; struct node{ int son1,son2,p; }same[M]; void dfs1(int u,int ff){ sz[u]=1,deep[u]=deep[ff]+1,dfn[u]=++cnt,fa[u]=ff; for(auto v:g[u]){ if(v!=ff){ dfs1(v,u); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } } } void dfs2(int u,int top){ tp[u]=top; if(son[u]) dfs2(son[u],top); for(auto v:g[u]){ if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } int LCA(int x,int y){ while(tp[x]!=tp[y]){ if(deep[tp[x]]>deep[tp[y]]) x=fa[tp[x]]; else y=fa[tp[y]]; } return deep[x]>deep[y]?y:x; } int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } bool cmp1(int x,int y){ if(deep[x]==deep[y]) return dfn[x]<dfn[y]; return deep[x]>deep[y]; } bool cmp2(node x,node y){ if(deep[x.p]==deep[y.p]) return dfn[x.p]<dfn[y.p]; return deep[x.p]>deep[y.p]; } int main(){ int n,rt; scanf("%d%d",&n,&rt); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int u,v,i=1;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v); g[v].pb(u); } dfs1(rt,0); dfs2(rt,rt); int m=0; for(int i=1;i<=n;i++){ if(a[i]) id[++m]=i; } sort(id+1,id+1+m,cmp1); ll ans=0; for(int fir=1;fir<=m;fir++){ int sec=fir; while(sec<=m&&deep[id[fir]]==deep[id[sec]]) sec++; sec--; for(int i=fir;i<=sec;i++) f[id[i]]=id[i],val[id[i]]=a[id[i]]; if(fir==sec){ ans+=max(1ll,a[id[fir]]-deep[id[fir]]); continue; } int tot=0; for(int i=fir;i<sec;i++){ int lca=LCA(id[i],id[i+1]); same[++tot].p=lca; same[tot].son1=id[i]; same[tot].son2=id[i+1]; f[lca]=lca; val[lca]=0; } sort(same+1,same+1+tot,cmp2); for(int i=1;i<=tot;i++){ int x=find(same[i].son1),y=find(same[i].son2); ll val1=0,val2=0; if(x!=same[i].p) val1=max(1ll,val[x]-(deep[x]-deep[same[i].p])); if(y!=same[i].p) val2=max(1ll,val[y]-(deep[y]-deep[same[i].p])); val[same[i].p]+=val1+val2; f[x]=f[y]=same[i].p; } ans+=max(1ll,val[same[tot].p]-deep[same[tot].p]); fir=sec; } printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/starve/p/12735709.html
