首先求出缩一个点 $x$ 的贡献，就是缩 $x$ 的父亲的贡献加上 $x$ 的子树多减少的深度
假设此时缩父亲的贡献已经考虑过了，那么 $x$ 的子树多减少的深度就是子树的节点数
注意此时要满足 $x$ 不是根节点或根节点的儿子，不然缩和没缩是一样的
设这个贡献为 $sum[x]$
然后把所有操作 $l,r,v$ 离线，遇到一个操作左端点就把 $v$ 插入 $set$，遇到右端点再取出，在过程中动态维护总贡献
考虑把每个当前加入的节点搞一个虚树
对于一次缩节点的操作，如果它不在虚树链上，只会影响 $x$ 与虚树的第一个交点的一条链，更上面的已经缩过了
设交点为 $u$，那么贡献就是 $sum[x]-sum[u]$
如果原本已经在虚树链上了，那么 $x$ 不会有贡献
现在问题是如何求与虚树的交点，考虑原本构造虚树的过程，把节点按 $dfn$ 排序，然后根据与前后节点的 $lca$ 确定具体连边
设前后节点为 $u,v$，如果 $LCA(u,x)=u$ 且 $LCA(v,x)=x$ 那么 $x$ 在虚树边 $(u,v)$ 上，不产生贡献
如果 $LCA(u,x)!=u$ 且 $LCA(v,x)=x$ 那么 $x$ 还是在虚树上 $v$ 到根的路径上，不产生贡献
如果 $LCA(u,x)=u$ 且 $LCA(v,x)!=x$ ，或者 $LCA(u,x)!=u$ 且 $LCA(v,x)!=x$ 那么说明 $x$ 有多出来一段不在虚树还没统计的贡献
显然多出来的一段是 $LCA(u,x),LCA(v,x)$ 中深度较大的节点 $p$ 与 $x$ 的一条链的贡献，贡献为 $sum[x]-sum[p]$
然后就可以写成代码实现了，但是发现对于前两种情况 $LCA(u,x),LCA(v,x)$ 中深度较大的节点 $p$ 就是 $x$，贡献其实就是 $sum[x]-sum[p]=0$
所以直接求 $p$ 就行，不用分情况讨论了
因为一个节点可以被多次插入，所以要用 $multiset$，$multiset$ 里节点按 $dfn$ 排序就可以直接找前驱后继了
具体看代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #include<set> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n,m,Q; vector <int> V[N],add[N],del[N]; int dfn[N],F[21][N],dep[N],sz[N],cnt; ll sum[N],ans; void dfs1(int x) { sz[x]=1; dfn[x]=++cnt; ans+=dep[x]-1; for(int i=1;i<=20;i++) F[i][x]=F[i-1][F[i-1][x]]; for(int v : V[x]) { if(v==F[0][x]) continue; F[0][v]=x; dep[v]=dep[x]+1; dfs1(v); sz[x]+=sz[v]; } } void dfs2(int x) { sum[x]=sum[F[0][x]]+(dep[x]>2)*sz[x]; for(int v : V[x]) if(v!=F[0][x]) dfs2(v); } inline int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[F[i][x]]>=dep[y]) x=F[i][x]; if(x==y) return x; for(int i=20;i>=0;i--) if(F[i][x]!=F[i][y]) x=F[i][x],y=F[i][y]; return F[0][x]; } //以上预处理一堆东西 struct dat{ int val,x; dat (int v=0,int xx=0) { val=v,x=xx; } inline bool operator < (const dat &tmp) const { return val<tmp.val; } }; multiset <dat> S; multiset <dat>::iterator it; inline int Find(int x)//求x与当前虚树的交点p { dat res; it=S.upper_bound(dat(dfn[x],x)); int lca; //注意上面的res和set里面的节点没有关系，只是为了方便更新res if(it!=S.end())//注意判越界 lca=LCA(x,(*it).x),res=max(res,dat(dep[lca],lca)); if(it!=S.begin()) lca=LCA(x, (*prev(it)).x ),res=max(res,dat(dep[lca],lca)); //上面的 prev(it) 是找到与it-1指针不同的最后一个位置 return res.x ? res.x : x; } int main() { n=read(),m=read(),Q=read(); int a,b,c; for(int i=1;i<n;i++) { a=read(),b=read(); V[a].push_back(b); V[b].push_back(a); } while(Q--) { a=read(),b=read(),c=read(); add[a].push_back(c); del[b+1].push_back(c); } dep[1]=1; dfs1(1); dfs2(1); S.insert(dat(dfn[1],1));//初始有根节点 for(int i=1;i<=m;i++) { for(int x : add[i]) { if(S.find(dat(dfn[x],x))==S.end()) ans-=(sum[x]-sum[Find(x)]);//第一次插入 S.insert(dat(dfn[x],x)); } for(int x : del[i]) { S.erase(S.find( dat(dfn[x],x) )); if(S.find(dat(dfn[x],x))==S.end()) ans+=(sum[x]-sum[Find(x)]);//同理 } printf("%lld ",ans); } printf(" "); return 0; }