感觉自己的数据结构水平比较差，而且对树上问题的很多思路和技巧没有学习，关于树形 \(DP\) 问题和换根法的话，另有博客讲解，于是开了这篇博客，记录一些树上问题的有价值的题目，以提高对树上问题的求解能力。
CF739B Alyona and a tree
题意
有一棵 \(n\) 个点的树，每条边有一个边权，每个点有一个值 \(a_i\) ，对于树上的每一个点 \(u\) ，求出在它的子树里面有多少个点满足到 \(u\) 的距离 \(\le a_i\) 。
\(1\le n\le 200000\)
Solution
这题其实比较水，但是这个转化贡献方式的思路会经常用到。
考虑树上倍增，预处理出倍增数组，枚举每个点 \(i\) ，找出这个点会对它的哪些祖先产生贡献，倍增向上跳，跳到第一个不满足条件的点，那从这个点到 \(i\) 这条链上的所有点都会被 \(i\) 贡献，且由于距离递增，这个点以上的所有点都不会被贡献，用一个树上差分对这条链打上标记，最后再做一遍树上 \(DFS\) 求出前缀和即可求出答案了。
时间复杂度 \(O(nlogn)\) 。
[省选联考2021] 宝石
给定一棵 \(n\) 个点的树，每个点上有一颗种类是 \(w_i\) 的宝石，宝石种类共 \(m\) 种，有一个收集器，按照 \(P_1,P_2,...,P_c\) 的先后顺序收集宝石（就是说必须收集了前面的，才会收集后面的），有 \(q\) 次询问 $(s,t) $ ，询问从 \(s\) 到 \(t\) 最多 能收集多少宝石，若当前走到的点的宝石与当前需要放入的宝石种类一致才可以收集（也可以选择不收集）。
保证 \(p\) 中的值互不相同。
\(1\le n,q\le2\times10^5\) ，\(1\le c,m\le5\times10^4\)，\(1\le w_i\le m\) 。
有启发性的部分分： \(m\le300\) 。
Solution
每组询问暴力模拟，向上到 \(lca\) ，再向下找匹配的宝石一步步走，复杂度 \(O(nq)\) ，期望得分 \(25\) 分。
若考虑每次只走一步，这样必然很劣，注意到 \(m\le300\) 的部分分，如果每次都能一步走到需要加入的宝石的位置，则优秀一些，于是考虑预处理 \(f[i][j]\) 表示点 \(i\) 的祖先中第一个宝石种类为 \(j\) 的位置，转移只需考虑父亲的信息以及自身的颜色，但注意到这样做的话，从 \(lca\) 到 \(t\) 的路径不能直接处理，所以我们先只讨论向上跳的情况，到这一步的话，预处理是 \(O(nm)\) ，向上最多跳 \(c\) 次，我们认为 \(c\) 与 \(m\) 同阶，复杂度是 \(O((n+q)m)\) ，若可以处理向下移动，则期望得分 \(50\) 分。
事实上，这一档部分分是很有启发性的，这些移动，无非是一个逼近 \(lca\) 的过程，你思考你是怎么在 \(log\) 时间求出 \(lca\) 的，自然考虑倍增。
为方便维护，我们将宝石重新编号，不在需要收集的 \(c\) 种宝石中的宝石编号为 \(0\) ，\(P_1,...,P_c\) 号宝石编号为 \(1,2,...,c\) ，这样处理，向上的路径只需要找当前编号 \(+1\) ，那现在考虑向下的路径，类似的，只需要找当前编号 \(-1\) （因为逆序），那么我们就处理两个倍增数组 \(f1[u][i],f2[u][i]\) ，分别表示从点 \(u\) 向上跳 \(2^i\) 步递增和递减到达的点，这时若发现从 \(s\) 开始走一个 \(f1[s][i]\) 仍然不超过 \(lca\) ，则将向上部分的答案 \(s1\) 加上 \(2^i\) （不是 \(1\) ），注意，此处 “跳一步” 指的并不是儿子跳到父亲，而是跳到下一个需要收集的宝石所在的树上位置，这个在树上只需在 \(dfs\) 过程中维护一个数组 \(t[i]\) 表示走到当前节点， 第 \(i\) 种宝石最后一次出现的位置，注意每次结束当前子树的 \(dfs\) 后，要把 \(t\) 数组复原（每次只修改一个位置，所以是 \(O(1)\) 复原）。现在我们需要解决的就是向下路径的问题，考虑二分答案 \(mid\) ，表示当前这次询问一共收集了多少宝石，那么，只需要从 \(t\) 开始向上找到第一个种类为 \(mid\) 的宝石（注意是重新编了号的），这个信息不正是 \(t\) 数组所维护的吗？所以我们只需要对询问进行离线，对每个节点 \(i\) 开一个 \(vector\) ，表示以 \(i\) 为终点的询问，每次 \(dfs\) 到这个点时，就解决这个 \(vector\) 的询问，因为这时的 \(t\) 数组存的也正是我们需要的信息，设第一个种类为 \(mid\) 的宝石是 \(x\) ，答案的判定只需看 \(x\) 是否能至少向上跳 \(mid-s1\) 步仍不超过 \(lca\) 即可。
事实上询问还有一个问题，就是需要找到从 \(s\) 开始，第一个能够匹配的宝石，也即种类为 \(P_1\) 的宝石，先走这样一步，再进行上述的一系列操作，这个信息仍然是我们的 \(t\) 数组维护的，但这些所有的维护信息写在同一个 \(dfs\) 里就会有些繁杂不清，所以两遍 \(dfs\) 即可维护上述所有信息。
二分里面需要倍增数组判定，故时间复杂度 \(O(nlog^2n+q)\) 。
#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define inf 1e7
using namespace std;
int pd,lca,l,r,ans[N],n,m,c,q,A,B,dep[N],t[N],flag,a[N],f[N][19],first[N],f1[N][19],f2[N][19];
vector<int>v[N];
struct node
{
int s,t,id;
};
vector<node>ask[N];
int read()
{
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
int tmp=t[a[u]];
t[a[u]]=u;first[u]=t[1];
f[u][0]=fa;f1[u][0]=t[a[u]+1];f2[u][0]=t[a[u]-1];
for(int i=1;i<=18;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
f1[u][i]=f1[f1[u][i-1]][i-1];
f2[u][i]=f2[f2[u][i-1]][i-1];
}
for(auto x:v[u])
{
if(x==fa) continue;
dfs(x,u);
}
t[a[u]]=tmp;
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=18;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
}
for(int i=18;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int check(int u,int mid)
{
u=t[mid];
if(dep[u]<dep[lca]) return 0;
for(int i=18;i>=0;i--)
{
if(dep[f2[u][i]]>=dep[lca]) u=f2[u][i],mid-=(1<<i);
if(mid<=pd) return 1;
}
return 0;
}
void dfs2(int u,int fa)
{
int tmp=t[a[u]];
t[a[u]]=u;
for(auto x:ask[u])
{
lca=LCA(x.s,x.t);
int now=0,val=0;
if(dep[first[x.s]]>=dep[lca]) now=first[x.s];
if(now)
{
val++;
for(int i=18;i>=0;i--)
{
if(dep[f1[now][i]]>=dep[lca]) now=f1[now][i],val+=(1<<i);
}
}
pd=val+1;
l=val+1;r=c;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(u,mid)) val=mid,l=mid+1;
else r=mid-1;
}
ans[x.id]=val;
}
for(auto x:v[u])
{
if(x==fa) continue;
dfs2(x,u);
}
t[a[u]]=tmp;
}
int main()
{
n=read();m=read();c=read();
for(int i=1;i<=c;i++) A=read(),t[A]=i;
for(int i=1;i<=n;i++) a[i]=read(),a[i]=t[a[i]];
memset(t,0,sizeof(t));
for(int i=1;i<=n-1;i++)
{
A=read();B=read();
v[A].push_back(B);
v[B].push_back(A);
}
dfs(1,0);
q=read();
for(int i=1;i<=q;i++)
{
A=read();B=read();
ask[B].push_back((node){A,B,i});
}
memset(t,0,sizeof(t));
dfs2(1,0);
for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
[AHOI2022] 钥匙
题意简述
给定一棵 \(n\) 个点的树，每个节点上要么有一把钥匙，要么有一个宝箱，且钥匙和宝箱都是有颜色的，有 \(m\) 次询问 \((u,v)\) ，表示走树上 \(u\) 到 \(v\) 的路径，若当前点是钥匙，则接受，若是宝箱，则查看之前接受的钥匙是否存在和宝箱颜色相同的，若存在，则得分 \(+1\) ，每组询问独立，求每组询问的得分。
\(1\le n\le5\times10^5\) ，\(1\le m\le1\times10^6\) ，每种颜色的钥匙均不超过 \(5\) 。
Solution
首先，题目给出的特殊条件一定是出发点，相信出题人是不会平白无故给你神奇的性质的。
你发现直接对 \((u,v)\) 进行计算是很困难的，这时候我们通常是考虑贡献的转化，把 “直接算出当前的答案” 转化为 “哪些路径的加分能够贡献当前询问的路径” ，于是只需考虑一条路径能够对哪些其他的路径产生影响，这样就实现了思路和贡献的转化。
具体地，我们首先可以想到，对出现的每一种颜色分开考虑，我们每次枚举点对只需进行树的 \(dfs\) 即可。
对于当前考虑的颜色 \(col\) 来说，将这种颜色的钥匙设为 \(1\) ，这种颜色的宝箱设为 \(-1\) ，其他颜色不同的点，不论是钥匙还是宝箱都设为 \(0\) ，这样的话，我们从一个点开始树上 \(dfs\) ，当找到一个点的路径和等于 \(0\) 时，我们就不必再继续搜索下面的节点了。
这是为啥呢？其实是为了避免算重，我们这样考虑，假设从 \(S\) 点开始搜索，这个最先遇到的路径和为 \(0\) 的节点是 \(T\) ，那么对于树上所有横跨了路径 \((S,T)\) 的路径，都是会被 \((S,T)\) 贡献的（当然，由于 \(T\) 是第一次为零的位置，也即只在这一个位置产生 \(1\) 的得分）。
之后，如果继续搜索，又遇到一个使其为零的节点 \(U\) ，这时的得分显然就是 \(2\) 了，如果仍然将横跨 \((S,U)\) 的路径被当前这个 \(2\) 的得分贡献，那么你思考，\(2\) 的贡献咋来的，还不是 \((S,T)\) 产生了 \(1\) 的贡献，所以其实 \((S,T)\) 的贡献被计算了两次，故我们每次搜索过程中，只考虑第一个遇到的路径和为 \(0\) 的节点，这样才会避免上述算重的情况，且这样做显然是能够计算所有贡献的。
回头看看这个按颜色进行 \(dfs\) 的过程，你发现每次只需要从那 \(5\) 个颜色相同的钥匙开始做，但这样还是和对每个点进行整棵树的搜索别无二致，仍然是 \(O(N^2)\) 的复杂度，那怎么办呢？假设当前枚举到红色，我们看下面一个图。
（图源：Bindir0的ppt）
从根部的红色搜索到底部的红色，需要经过大量的蓝色点，但我们只关心第一次搜索到的位置，所以中间的大量蓝色点，我们是完全没有必要去搜索的，也就是说，每次只需要一部分关键节点，所以我们对每个颜色的关键点建出对应的虚树。
虚树，也即只保留关键点和他们的 \(LCA\) ，这样就维护了原本的信息结构，使得本来应该在某个点之后被搜索到的点仍然在其之和被搜索到，且节省了大量无用节点。
这样可知，每轮最多对虚树遍历 \(5\) 次，设有 \(k\) 个关键点，则虚树大小是 \(klogk\) 的，则总共也就是 \(nlogn\) 级别的。
下一个问题，如何将当前的 \(1\) ，贡献到横跨了 \((S,T)\) 的路径上去呢？
这个问题我们分三种情况讨论。
第一种，若 \(T\) 在 \(S\) 的子树内，则 \(S\) 除 \(T\) 所在子树的其他子树的所有点到 \(T\) 子树中的所有点构成的路径，都会被 \((S,T)\) 贡献 \(1\) ，也就是说，设 \(S\) 向 \(T\) 的方向的儿子为 \(son\) ，以 \(son\) 为根的子树内最大的 \(dfn\) 的值为 \(end[son]\) ，那么区间 \([1,dfn[son]-1]∪[end[son]+1,n]\) 中的点向区间 \([dfn[T],end[T]]\) 中的点行走时，都会被路径 \((S,T)\) 贡献。
第二种，若 \(S\) 在 \(T\) 的子树内，又设 \(T\) 向 \(S\) 的方向的儿子为 \(son\) ，于是同理有点集 \([dfn[S],end[S]]\) 到点集 \([1,dfn[son]-1]∪[end[son]+1,n]\) 会被 \((S,T)\) 贡献。
第三种， \(S,T\) 不存在祖先关系，也即前两种情况都不满足，这种情况反而更加简单，这时候只需 \(S\) 子树任意一点到 \(T\) 子树任意一点的路径，显然都会被贡献，也即点集 \([dfn[S],end[S]]\) 和点集 \([dfn[T],end[T]\) 。会被 \(S,T\) 贡献。
如何维护呢？我们用一个 \(n\times n\) 矩形来代表我们维护的任意两个点对的值，也即维护 \(A[i][j]\) ，表示 \(i\) 走到 \(j\) 的答案。
那么对于我们上述三种情况的讨论，我们只需执行对应的矩形加即可，也即把上述讨论中的两个区间，看成子矩形的边界，你发现没有修改，所以只需做二维差分，最后算每一行的总和时，使用一个树状数组维护即可，对于一个查询，实际上就是查询一个点值，由于维护的是差分，所以查的是前缀和。
时间复杂度 \(O((5n+m)logn)\) ，下面是我的代码。
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define mp make_pair
using namespace std;
int A,B,s[N],c[N],top[N],ans[N],rev[N],z,now,tot,f[N],cnt,dfn[N],n,m,op[N],col[N],dep[N],siz[N],son[N];
char *p1,*p2,buf[100000];
#define getc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x=0,f=1;char ch=getc();
while(ch<48||ch>57){if(ch=='-')f=-1;ch=getc();}
while(ch>=48&&ch<=57){x=x*10+ch-48,ch=getc();}
return x*f;
}
vector<int>v[N],G[N],tmp,vec[N];
vector<pair<int,int> >val[N],q[N];
void dfs1(int u,int fa)
{
dep[u]=dep[fa]+1;siz[u]=1;
f[u]=fa;
for(auto x:G[u])
{
if(x==fa) continue;
dfs1(x,u);
siz[u]+=siz[x];
if(siz[x]>siz[son[u]]) son[u]=x;
}
}
void dfs2(int u,int t)
{
top[u]=t;dfn[u]=++cnt;rev[cnt]=u;
if(son[u]) dfs2(son[u],t);
for(auto x:G[u])
{
if(x==f[u]||x==son[u]) continue;
dfs2(x,x);
}
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
return x;
}
int cmp(int x,int y){return dfn[x]<dfn[y];}
void Add(int s,int e){vec[s].push_back(e);vec[e].push_back(s);}
void build(int u)
{
sort(v[u].begin(),v[u].end(),cmp);
for(auto x:v[u])
{
tmp.push_back(x);
if(!tot)
{
s[++tot]=x;
continue;
}
int now=LCA(s[tot],x);
while(tot>1&&dep[s[tot-1]]>=dep[now]) Add(s[tot-1],s[tot]),tot--;
if(s[tot]!=now)
{
Add(s[tot],now);s[tot]=now;
tmp.push_back(now);
}
s[++tot]=x;
}
while(tot>1) Add(s[tot-1],s[tot]),tot--;
}
int check(int x,int y)
{
if(dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+siz[x]-1) return 1;
else return 0;
}
int find(int x,int y)
{
int pre=0;
while(top[x]^top[y])
{
pre=top[x];
x=f[top[x]];
}
if(x==y) return pre;
return rev[dfn[y]+1];
}
void modify(int a,int b,int c,int d)
{
if(a>b||c>d) return;
val[a].push_back(mp(c,1));val[a].push_back(mp(d+1,-1));
val[b+1].push_back(mp(c,-1));val[b+1].push_back(mp(d+1,1));
}
void add(int x,int y)
{
if(check(x,y))
{
int z=find(y,x);
modify(1,dfn[z]-1,dfn[y],dfn[y]+siz[y]-1);
modify(dfn[z]+siz[z],n,dfn[y],dfn[y]+siz[y]-1);
}
else if(check(y,x))
{
int z=find(x,y);
modify(dfn[x],dfn[x]+siz[x]-1,1,dfn[z]-1);
modify(dfn[x],dfn[x]+siz[x]-1,dfn[z]+siz[z],n);
}
else modify(dfn[x],dfn[x]+siz[x]-1,dfn[y],dfn[y]+siz[y]-1);
}
void dfs(int u,int pre,int s)
{
if(s<0) return;
for(auto x:vec[u])
{
if(x==pre) continue;
if(op[x]==2&&col[x]==z&&s==0)
{
add(now,x);
continue;
}
int d=0;
if(col[x]==z)
{
if(op[x]==1) d++;
else d--;
}
dfs(x,u,s+d);
}
}
int lowbit(int x){return x&(-x);}
void update(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=val;
}
int query(int x)
{
int sum=0;
for(int i=x;i>=1;i-=lowbit(i)) sum+=c[i];
return sum;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
op[i]=read();col[i]=read();
v[col[i]].push_back(i);
}
for(int i=1;i<=n-1;i++)
{
A=read();B=read();
G[A].push_back(B);
G[B].push_back(A);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++)
{
if(!(int)v[i].size()) continue;
build(i);z=i;
for(auto x:v[i])
{
if(col[x]==i&&op[x]==1) now=x,dfs(x,0,0);
}
for(auto x:tmp) vec[x].clear();
tmp.clear();
tot=0;
}
for(int i=1;i<=m;i++)
{
A=read();B=read();
q[dfn[A]].push_back(mp(dfn[B],i));
}
for(int i=1;i<=n;i++)
{
for(auto x:val[i]) update(x.first,x.second);
for(auto x:q[i]) ans[x.second]=query(x.first);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}