树型问题总结
Published:
树型问题总结
1. 点分治
$Des:$ 点分治用于处理树上路径问题，多用于查询路径问题的存在性以及路径问题的计数，其核心思想就是将每条路径的两个端点拆分到两个不同子树中，即通过分治中心将两个端点分开到两个不同的子树中。而统计答案的操作类似于 $CDQ$ 分治，计算两个分治区间之间的影响。
为了保证我们的分治次数，我们使用了重心的性质，每次动态找分治区间的重心(这一步得非常小心，极有可能导致答案错误)。由于重心保证了每个子树大小不超过原树的 $\frac{1}{2}$ ，所以可以得到，我们的分治次数是 $O(logn)$ 级别。而基本上，每次分治，我们都访问了整棵树，所以分治的总复杂度 $O(nlogn)$ 。
而所有能套用点分治的操作，都有一个要求：对于两个分治区间之间的影响，我们能快速得到。至于这一步，常用的方法就是单调栈、单调队列以及二分，以保证我们在分治后统计答案的时间复杂度在 $O(1)$ 到$O(logn)$ 级别。
因此，算是分治与统计答案的总复杂度，点分治的总时间复杂度大致应该在 $O(nlogn)$ 到 $O(nlog^2n)$ 。属于比较高效的算法。
以下代码为：询问树上长度为 $k$ 的路径是否存在。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define FOR(i,a,b) for(re int i=(a),i##i=(b) ; i<=i##i ; ++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b) ; i>=i##i ; --i)
#define gc getchar()
//#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
using namespace std;
const int N=2e5+10,mo=1e9+7;
char *fs,*ft,buf[1<<18];
LL read(){
ll p=0; char ch=gc; bool w=0;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
struct ao{
int dis,id;
}a[N],q[N];
vector<int>tr[N],vl[N];
int n,m,rt,sum,tot;
int siz[N],mx[N],vis[N],ans[N];
I cmp(ao s,ao t){ return s.dis<t.dis;}
V get_rt(int u,int fa){
siz[u]=1,mx[u]=0;
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(v==fa||vis[v]) continue;
get_rt(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u],sum-siz[u]);
if(mx[u]<mx[rt]) rt=u;
return ;
}
V dfs(int u,int fa,int dis,int id){
a[++tot].dis=dis,a[tot].id=id,siz[u]=1;
int z=tr[u].size(),v=0,w=0;
FOR(i,0,z-1){
v=tr[u][i],w=vl[u][i];
if(vis[v]||v==fa) continue;
dfs(v,u,dis+w,id);
siz[u]+=siz[v];
}
return ;
}
V cal(int u){
int z=tr[u].size(),v=0,w=0;
a[tot=1].dis=0,a[tot].id=u,siz[u]=1;
FOR(i,0,z-1){
v=tr[u][i],w=vl[u][i];
if(vis[v]) continue;
dfs(v,u,w,v);
siz[u]+=siz[v];
}
sort(a+1,a+1+tot,cmp);
FOR(i,1,m){
int l=1,r=tot;
while(l<r){
if(ans[q[i].id]) break;
if(a[l].dis+a[r].dis<q[i].dis) ++l;
else if(a[l].dis+a[r].dis>q[i].dis) --r;
else if(a[l].id==a[r].id) a[r].id==a[r-1].id?--r:++l;
else ans[q[i].id]=1;
}
}
return ;
}
V sol(int u){
vis[u]=1,cal(u);
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(vis[v]) continue;
sum=siz[v],rt=0,get_rt(v,v);
sol(rt);
}
return ;
}
int main(){
int x,y,z;
n=read(),m=read();
FOR(i,2,n){
x=read(),y=read(),z=read();
tr[x].push_back(y),tr[y].push_back(x);
vl[x].push_back(z),vl[y].push_back(z);
}
FOR(i,1,m) q[i].dis=read(),q[i].id=i;
sort(q+1,q+1+m,cmp);
mx[0]=n+1,sum=n,rt=0,get_rt(1,1),sol(rt);
FOR(i,1,m) ans[i]?printf("AYE\n"):printf("NAY\n");
return 0;
}
2. 长链剖分
$Des:$ 长链剖分本质上就是另外一种链剖分方式，通常用于优化有关深度的 $dp$ 操作。其优秀的时空复杂度使其受广大 $OIer$ 喜爱。
长剖类似重剖，定义了轻重链/儿子，不过不同于重剖，长剖以子节点深度作为关键字。可以发现，任意点到根节点路径上的轻链个数不超过 $\sqrt n$ 。
长剖优化有关深度的 $dp$ 的精髓就在于对指针的运用。我们对于每个节点，先访问它的重儿子，然后直接继承其答案，同时，这里的继承也可能需要由儿子先继承父亲值，而这里也有个细节需要注意：一般有关深度的 $dp$ ，我们都是直接把儿子节点的信息继承到父亲节点的深度更后面一位的位置，所以可以使用长剖优化，但是对于其他情况的继承，也可能可以用更高妙的方式进行继承，这里不展开。
然后就是正常地对于其他子树地计算，然后合并答案，这里需要留意的是：利用指针给其他子树分配大小为它深度的空间。然后根据深度进行 $dp$ 。
绝大多数情况下，长剖的时间复杂度是优秀的 $O(n)$ 。有时，用于优化其他算法的时候，也可能出现 $nlogn$ 的预处理， $O(1)$ 的查询，例如求 $k$ 级祖先，我们就是倍增加上长剖进行 $O(nlogn)$ 的预处理，然后 $O(1)$ 查询。
以下代码为：给定一棵树，在树上选 $3$ 个点，要求两两距离相等，求方案数。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define FOR(i,a,b) for(re int i=(a),i##i=(b) ; i<=i##i ; ++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b) ; i>=i##i ; --i)
#define gc getchar()
//#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
using namespace std;
const int N=2e4+10;
char *fs,*ft,buf[1<<18];
LL read(){
ll p=0; char ch=gc; bool w=0;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
vector<int>tr[N];
int n,fa[N],dep[N],son[N];
V dfs1(int u){
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(v==fa[u]) continue;
fa[v]=u,dfs1(v);
if(dep[v]>dep[son[u]]) son[u]=v;
}
dep[u]=dep[son[u]]+2;
return ;
}
ll ans,us1[N],us2[N],*now1=us1,*now2=us2,*f[N],*g[N];
V dfs2(int u){
int z=tr[u].size(),v=0;
f[u][0]=1;
if(son[u]){
v=son[u],f[v]=f[u]+1,g[v]=g[u]-1;
dfs2(v);
ans+=g[u][0];
}
FOR(i,0,z-1){
v=tr[u][i];
if(v==fa[u]||v==son[u]) continue;
f[v]=now1,now1+=dep[v];
now2+=dep[v],g[v]=now2,now2+=dep[v];
dfs2(v);
FOR(j,1,dep[v]-1) ans+=f[u][j-1]*g[v][j],ans+=g[u][j]*f[v][j-1];
FOR(j,1,dep[v]-1) g[u][j]+=f[u][j]*f[v][j-1],g[u][j-1]+=g[v][j],f[u][j]+=f[v][j-1];
}
return ;
}
int main(){
int x,y;
n=read();
FOR(i,2,n) x=read(),y=read(),\
tr[x].push_back(y),\
tr[y].push_back(x);
dfs1(1),f[1]=now1,now1+=dep[1],now2+=dep[1],g[1]=now2,now2+=dep[1],dfs2(1);
printf("%lld",ans);
return 0;
}
3. $kruskal$ 重构树
$Des:$ $kruskal$ 重构树用于处理存在形如 “路径上边权最大值小于等于 $x$ “样的限制的图论问题。
$kruskal$ 重构树的核心思想是基于 $kruskal$ 最小生成树的算法，每次找最小的边，然后建一个点权为当前边权的节点，将原边的两端点连接，这里需要注意：这一步操作，我们相当于在并查集中把两端点归到了新节点中。
而根据我们的构造方式， $kruskal$ 重构树它拥有如下性质：1.重构的树为二叉堆；2.原树两点之间的边权最大值的最小值是重构树上两点的 $lca$ 的权值；3.重构树中叶子节点代表原节点，而其他节点代表边。事实上，我们在建重构树的时候，丢失了原图很多信息，而如果我们需要使用 $kruskal$ 重构树，那我们必须保证这些信息是无用的。而我们保留的信息仅是图上两点之间的联通性，以及两点之间的路径最大权值的最小值，或者说，我们保留了到点 $x$ 路径上最大值小于等于 $val$ 的节点信息—— $x$ 祖先相应小于等于 $val$ 的节点的叶子节点。
当我们建出了 $kruskal$ 重构树之后(时间复杂度 $O(nlogn)$)，很多问题就变得好解多了，剩余的部分可能就需要运用其他工具例如 $LCT$ 进行维护了，这里不进行赘述。
以下代码为：$n$ 个点的无向图中询问两点路径最大权值的最小值。
#include<bits/stdc++.h>
#define ll long long
#define re register
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
//#define gc getchar()
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
using namespace std;
const int N=2e5+10;
char *fs,*ft,buf[1<<18];
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-',ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int n,m,K;
struct Edge {int a,b,w;} e[N];
inline bool operator < (const Edge &A,const Edge &B) {return A.w<B.w;}
int f[N],val[N];
inline int Find(int x) {return x==f[x]?x:f[x]=Find(f[x]);}
struct Branch {int next,to;} ed[N];
int h[N],cnt=0;
V add(int x,int y) { ed[++cnt].to=y; ed[cnt].next=h[x]; h[x]=cnt; }
void Ex_Kruskal() {
int ind=n,lim=n<<1; sort(e+1,e+1+m);
FOR(i,1,lim) f[i]=i;
FOR(i,1,m){
int fx=Find(e[i].a),fy=Find(e[i].b);
if(fx!=fy) {
f[fx]=f[fy]=++ind;
val[ind]=e[i].w;
add(ind,fx); add(ind,fy);
if(ind==lim-1) break;
}
}
return ;
}
int size[N],deep[N];
int top[N],fa[N],son[N];
V Dfs1(int v,int pre,int dep) {
size[v]=1; fa[v]=pre; deep[v]=dep;
for(int i=h[v];i;i=ed[i].next) {
int j=ed[i].to;
Dfs1(j,v,dep+1); size[v]+=size[j];
if(size[son[v]]<size[j]) son[v]=j;
}
return ;
}
V Dfs2(int v,int T) {
top[v]=T; if(son[v]) Dfs2(son[v],T);
for(int i=h[v];i;i=ed[i].next) {
int j=ed[i].to;
if(j^fa[v]&&j^son[v]) Dfs2(j,j);
} return ;
}
inline int Ask(int x,int y) {
while(top[x]!=top[y]) deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]];
return deep[x]<deep[y]?val[x]:val[y];
}
int main() {
n=read(); m=read(); K=read();
FOR(i,1,m){
int a=read(),b=read(),w=read();
e[i]=(Edge){a,b,w};
}
Ex_Kruskal(); Dfs1((n<<1)-1,0,1); Dfs2((n<<1)-1,(n<<1)-1);
FOR(i,1,K) cout<<Ask(read(),read())<<'\n';
return 0;
}
4. $dsu\ on\ tree$
$Des:$ 对于询问子树且不存在修改操作的问题，我们多会用到 $dsu\ on\ tree$ 对我们的暴力算法进行优化。$dsu\ on\ tree$ 是基于重剖的启发式优化。
该算法的核心思想为，当我们需要预处理某些子树信息的时候，父亲与儿子节点的答案中存在继承关系(这里类似于长剖的继承)，我们就对树进行剖分，每次只保留重儿子的贡献，而其他儿子的贡献先扔掉。这里有一点值得注意的是：这里的继承重儿子的贡献是指，保留重儿子子树的贡献，而非重链的贡献(当时在这个地方思考了很长时间)。而由于重剖的性质，我们成功地将时间复杂度由 $O(n^2)$ 降到了 $O(nlogn)$ 。
以下代码为：给出一个大小为 $n$ 的树，求出每个节点的子树中出现次数最多的颜色的编号和。
#include<bits/stdc++.h>
#define ll long long
#define re register
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define gc getchar()
//#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
using namespace std;
const int N=2e5+10;
char *fs,*ft,buf[1<<18];
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-',ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int n,col[N],son[N], siz[N], cnt[N], Mx, Son;
LL sum = 0, ans[N];
vector<int>tr[N];
V dfs(int x, int fa) {
int z=tr[x].size();
siz[x] = 1;
FOR(i,0,z-1){
int to = tr[x][i];
if(to == fa) continue;
dfs(to, x);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;//轻重链剖分
}
return ;
}
V add(int x, int fa, int val) {
cnt[col[x]] += val;//这里可能会因题目而异
if(cnt[col[x]] > Mx) Mx = cnt[col[x]], sum = col[x];
else if(cnt[col[x]] == Mx) sum += (LL)col[x];
int z=tr[x].size();
FOR(i,0,z-1){
int to = tr[x][i];
if(to == fa || to == Son) continue;
add(to, x, val);
}
return ;
}
V dfs2(int x, int fa, int opt) {
for(int i = 0; i < tr[x].size(); i++) {
int to = tr[x][i];
if(to == fa) continue;
if(to != son[x]) dfs2(to, x, 0);//暴力统计轻边的贡献，opt = 0表示递归完成后消除对该点的影响
}
if(son[x]) dfs2(son[x], x, 1), Son = son[x];//统计重儿子的贡献，不消除影响
add(x, fa, 1); Son = 0;//暴力统计所有轻儿子的贡献
ans[x] = sum;//更新答案
if(!opt) add(x, fa, -1), sum = 0, Mx = 0;//如果需要删除贡献的话就删掉
return ;
}
int main() {
int x,y;
n=read();
FOR(i,1,n) col[i] = read();
FOR(i,2,n) x=read(),y=read(),\
tr[x].push_back(y),\
tr[y].push_back(x);
dfs(1, 0);
dfs2(1, 0, 0);
FOR(i,1,n) printf("%lld ",ans[i]);
return 0;
}
5.虚树
$Des:$ 虚树是个强大的数据结构，用于解决树上关键点问题，一般题面中会用形如 $\sum m\le1e5$ 的字眼提示我们，此题需要使用虚树。虚树的强大之处在于，它极简地只维护了关键点信息，其他节点信息几乎全部丢失。
虚树建立的核心思想在于：我们按 $dfs$ 序加入关键点，这样就保证了加入点的有序性，而加入 $lca$ 的操作就是为了保证树结构的完整性。为了尽可能低复杂度的加入关键点，我们用 $dfs$ 序加入节点相当于在分割原树。我们用栈保存当前部分的节点，其他节点已经加入虚树中且它们已经在当前枚举的分割线的左部分了。加入节点就是找当前节点与栈顶元素的 $lca$ ，然后根据 $lca$ 的位置弹栈(边弹栈边连边)更新当前枚举分割线。当我们用 $nlogn$ 的时间预处理 $lca$ 以及使用归并排序可以将建虚树的复杂度降到 $O(m)$ ，但是绝大多数情况下 $O(mlogm)$ 就已经够用了，而且其更好写。
一般当我们建好虚树之后，我们可能会用到 $LCT$ 进行维护，或优化 $dp$ ，而优化 $dp$ 的时候又多会使用到树上倍增。时间复杂度一般为 $O(nlogn)$ 。
以下代码为 $[HNOI2014]$ 世界树。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define REP(i,u) for(re int i=hd[u],v=ed[i].to;i;i=ed[i].nx,v=ed[i].to)
//#define gc getchar()
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),ft==fs))?0:*fs++
#define fs first
#define sc second
using namespace std;
char *fs,*ft,buf[1<<18];
const int N=3e5+10,inf=1e9+7;
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
struct ao{
int nx,to;
}ed[N];
struct in{
int w,id;
}a[N];
vector<int>tr[N];
int n,q,m,fl,id;
int ans[N],as[N];
int dfn[N],vis[N],siz[N],hd[N],fa[N][21],dep[N],s[N],tp;
V add(int u,int v){ ed[++fl]=(ao){hd[u],v},hd[u]=fl;}
V dfs1(int u){
dfn[u]=++id,siz[u]=1;
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(v==fa[u][0]) continue;
fa[v][0]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
}
return ;
}
I lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
ROF(k,18,0) if(dep[fa[x][k]]>=dep[y]&&fa[x][k]) x=fa[x][k];
if(x==y) return x;
ROF(k,18,0) if(fa[x][k]!=fa[y][k]&&fa[x][k]) x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
typedef pair<int,int> PI;
PI f[N];
int ff[N],sz[N];
V dfs2(int u){
if(vis[u]) f[u]=make_pair(0,u);
PI tmp;
REP(i,u) dfs2(v),tmp=f[v],tmp.fs+=dep[v]-dep[u],f[u]=min(f[u],tmp);
return ;
}
V dfs3(int u,int dis,int p){
if(make_pair(dis,p)<f[u]) f[u]=make_pair(dis,p);
else dis=f[u].fs,p=f[u].sc;
REP(i,u) dfs3(v,dis+dep[v]-dep[u],p);
}
I get(int u){
int x=u;
ROF(k,18,0) if(dep[fa[x][k]]>dep[ff[u]]&&fa[x][k]) x=fa[x][k];
return x;
}
V dfs4(int u){
int x=u;
REP(i,u) dfs4(v);
if(fl&&ff[u]) x=get(u),sz[ff[u]]+=siz[x];
return ;
}
V dfs5(int u){
ans[f[u].sc]+=siz[u]-sz[u];
REP(i,u) dfs5(v);
}
V dfs6(int u){
int x,y;
PI tmp1,tmp2;
REP(i,u){
if(f[u]==f[v]) x=get(v),ans[f[u].sc]+=siz[x]-siz[v];
else{
x=v;
ROF(k,18,0){
if(dep[fa[x][k]]<dep[u]||!fa[x][k]) continue;
tmp1=f[v],tmp1.fs+=dep[v]-dep[fa[x][k]];
tmp2=f[u],tmp2.fs+=dep[fa[x][k]]-dep[u];
if(tmp1<tmp2) x=fa[x][k];
}
y=get(v);
ans[f[u].sc]+=siz[y]-siz[x];
ans[f[v].sc]+=siz[x]-siz[v];
}
dfs6(v);
}
return ;
}
B cmp(in x,in y){ return dfn[x.w]<dfn[y.w];}
int sck[N],cnt;
int main(){
int x,y;
n=read();
FOR(i,2,n) x=read(),y=read(),\
tr[x].push_back(y),\
tr[y].push_back(x);
dfs1(1);
FOR(k,1,18) FOR(i,1,n) fa[i][k]=fa[fa[i][k-1]][k-1];
q=read();
FOR(i,1,n) f[i]=make_pair(inf,inf);
FOR(i,1,q){
m=read();
FOR(j,1,m) a[j].w=read(),vis[a[j].w]=1,a[j].id=j;
sort(a+1,a+1+m,cmp);
s[tp=1]=1,sck[cnt=1]=1,fl=0;
FOR(j,1,m){
int x=a[j].w,y=lca(x,s[tp]);
if(x==1) continue;
sck[++cnt]=x,sck[++cnt]=y;
while(tp>1&&dep[s[tp-1]]>=dep[y])
add(s[tp-1],s[tp]),ff[s[tp]]=s[tp-1],--tp;
if(s[tp]!=y) add(y,s[tp]),ff[s[tp]]=y,s[tp]=y;
s[++tp]=x;
}
while(tp>1) add(s[tp-1],s[tp]),ff[s[tp]]=s[tp-1],--tp;
dfs2(1);
dfs3(1,f[1].fs,f[1].sc);
dfs4(1);
dfs5(1);
dfs6(1);
FOR(j,1,m) as[a[j].id]=ans[a[j].w];
FOR(j,1,m) printf("%d ",as[j]);
printf("\n");
FOR(j,1,cnt) vis[sck[j]]=hd[sck[j]]=0,\
sz[sck[j]]=ans[sck[j]]=ff[sck[j]]=0,\
f[sck[j]]=make_pair(inf,inf);
sz[0]=0;
}
return 0;
}
6.最小割树
$Des:$ 最小割树是用于处理无向图上两点之间的最小割问题。最小割树的构造是递归实现的。
在当前点集随意选取两个点 $u,v$，在原图上跑出他们之间的最小割，然后就在树上连一条从 $u$ 到 $v$ ,权值为 $\lambda(u,v)$ 的边。
以下代码为最小割树的模板。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define inf 99999999
#define ll long long
#define LL inline ll
#define V inline void
#define I inline int
#define re register
#define FOR(i,a,b) for(re int i=a ; i<=b ; ++i)
#define ROF(i,a,b) for(re int i=a ; i>=b ; --i)
//#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++
#define gc getchar()
#define REP(i,u) for(re int i=head[u],v=edge[i].to;i!=-1;i=edge[i].nx,v=edge[i].to)
using namespace std;
const int N=600;
char buf[1<<15],*fs,*ft;
LL read(){
ll w=0,p=0;
char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
V write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return ;
}
int n,m,s,t,q,fl=-1,ans,mxfl;
int head[N],cur[N],dep[N];
vector<int>tr[N],w[N];
struct ao{
int nx,to,flow;
}edge[N*500],ed[N*500];
V add(int from,int to,int flow){
ed[++fl]=(ao){head[from],to,flow};head[from]=fl;
ed[++fl]=(ao){head[to],from,flow};head[to]=fl;
}
queue<int>Q;
I bfs(int s,int t){
int u=0;
FOR(i,1,n) dep[i]=inf,cur[i]=head[i];
dep[s]=0,Q.push(s);
while(Q.size()){
u=Q.front(),Q.pop();
REP(i,u) if(dep[v]>=inf&&edge[i].flow) dep[v]=dep[u]+1,Q.push(v);
}
if(dep[t]>=inf) return 0;
return 1;
}
I dfs(int u,int t,int limit){
if(!limit || u==t) return limit;
int mflow=0,f=0;
for(re int i=cur[u],v=edge[i].to;i!=-1;i=edge[i].nx,v=edge[i].to){
cur[u]=i;
if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(limit,edge[i].flow) ) ) ){
mflow+=f,limit-=f;
edge[i].flow-=f,edge[i^1].flow+=f;
if(!limit) break;
}
}
return mflow;
}
V Dinic(){ while(bfs(s,t)) mxfl+=dfs(s,t,inf);}
int sck[N],cnt,siz,vis[N];
V build(){
int sck1[N],sck2[N],cnt1=0,cnt2=0;
memset(vis,0,sizeof(vis));memcpy(edge,ed,sizeof(edge));
s=sck[1],t=sck[2];mxfl=0;Dinic();
tr[s].push_back(t),w[s].push_back(mxfl);
tr[t].push_back(s),w[t].push_back(mxfl);
FOR(i,1,cnt){
if(dep[sck[i]]<inf) sck1[++cnt1]=sck[i];
else sck2[++cnt2]=sck[i];
}
cnt=cnt1;
FOR(i,1,cnt) sck[i]=sck1[i];
if(cnt>1) build();
cnt=cnt2;
FOR(i,1,cnt) sck[i]=sck2[i];
if(cnt>1) build();
}
int mp[N][N];
V dfs(int x,int u,int fa,int sum){
int z=tr[u].size(),v=0,ww=0;
mp[x][u]=sum;
FOR(i,0,z-1){
v=tr[u][i],ww=w[u][i];
if(v==fa) continue;
dfs(x,v,u,min(ww,sum));
}
return ;
}
int main(){
int x,y,z;
n=read(),m=read();
FOR(i,1,n) head[i]=-1;
FOR(i,1,m){
x=read(),y=read(),z=read();
add(x,y,z);
}
FOR(i,1,n) sck[++cnt]=i;
build();
FOR(i,1,n) dfs(i,i,i,inf);
q=read();
FOR(i,1,q){
x=read(),y=read();
write(mp[x][y]),putchar('\n');
}
return 0;
}
7.换根 $dp$
$Des:$ 换根 $dp$ 通常用于处理树上不定根问题，当然，对于定根问题，有时也可以换根 $dp$ 。同时，换根 $dp$ 的使用条件为：由节点 $u$ 换根到节点 $v$ 时，我们需要维护的值需要能快速转换(一般需要预处理)，转换的时间复杂度一般要求在 $O(1)$ 到 $O(logn)$ 之间。
通常换根 $dp$ 都需要配合树上倍增来用，但是由于倍增是静态的，所以，我们在换根的时候，需要特别注意倍增数组，父亲数组，儿子数组，子树大小数组的转移。
以下代码为 $[CSP2019]$ 树的重心：$\displaystyle \sum(\sum_{x为S’u的重心}x+\sum{y为S’_v的重心}y)$
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define FOR(i,a,b) for(re int i=(a),i##i=(b) ; i<=i##i ; ++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b) ; i>=i##i ; --i)
#define gc getchar()
using namespace std;
const int N=3e5+10;
LL read(){
ll p=0; char ch=gc; bool w=0;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
vector<int>tr[N];
int T,n,son[N],son2[N],siz[N],f[N][20];
ll ans;
int tmp[N],ss[N],fa[N],tf[N];
V dfs1(int u,int ff){
siz[u]=1,fa[u]=ff;
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(v==ff) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son2[u]=son[u],son[u]=v;
else if(siz[v]>siz[son2[u]]) son2[u]=v;
}
tmp[u]=son[u],ss[u]=siz[u],tf[u]=fa[u],f[u][0]=son[u];
FOR(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
return ;
}
LL get(int u,int sum){ return max(ss[tmp[u]],sum-ss[u])<=sum/2?u:0; }
V dfs2(int u,int ff){
int z=tr[u].size(),v=0;
FOR(j,0,z-1){
v=tr[u][j];
if(v==ff) continue;
ss[u]=siz[1]-siz[v],tf[u]=tf[v]=0;
if(son[u]==v) tmp[u]=son2[u];
else tmp[u]=son[u];
if(ss[ff]>ss[tmp[u]]) tmp[u]=ff;
f[u][0]=tmp[u];
FOR(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
int us=u;
ROF(i,18,0) if(ss[u]-ss[f[us][i]]<=ss[u]/2) us=f[us][i];
ans+=get(us,ss[u])+get(tf[us],ss[u])+get(tmp[us],ss[u]);
us=v;
ROF(i,18,0) if(ss[v]-ss[f[us][i]]<=ss[v]/2) us=f[us][i];
ans+=get(us,ss[v])+get(tf[us],ss[v])+get(tmp[us],ss[v]);
tf[u]=v;
dfs2(v,u);
}
tmp[u]=son[u],ss[u]=siz[u],tf[u]=fa[u],f[u][0]=son[u];
FOR(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
return ;
}
V init(){
memset(tr,0,sizeof(tr)),memset(son2,0,sizeof(son2));
memset(f,0,sizeof(f)),memset(son,0,sizeof(son)),ans=0;
return ;
}
int main(){
int x,y;
T=read();
while(T--){
init();
n=read();
FOR(i,2,n) x=read(),y=read(),tr[x].push_back(y),tr[y].push_back(x);
dfs1(1,0),dfs2(1,0);
printf("%lld\n",ans);
}
return 0;
}
//2
//5
//1 2
//2 3
//2 4
//3 5
//7
//1 2
//1 3
//1 4
//3 5
//3 6
//6 7
8.树上 $dfs$ 序/欧拉序运用
$Des:$ 使用 $dfs$ 序以及欧拉序，可以将树上问题转化为序列问题，而对于序列问题，我们更好使用数据结构对其进行维护。在 $dfs$ 序以及欧拉序中，一个点的子树处于一段连续的区间之内。此技巧可以用于处理子树和、树链和的修改及询问问题，在一定程度上，可以取代树剖和 $LCT$ 。以下分多钟情况讨论。
1.点修改，子树和查询
此情况为最基本的情况，原问题在树状数组上相当于单点修改，区间查询。
add(l[x],k);
ask(r[x])-ask(l[x]-1);
2.树链修改，单点查询
由于树链修改，以至于我们不便于直接维护真实值，因此，这里将单点权值修改为子树权值和，即，对于子树权值和取差分。那么，我们每个点的修改就只对其祖先节点产生影响，而对于祖先节点的查询，就变成了区间查询。
add(l[x],k),add(l[y],k),add(l[lca(x,y)],-k),add(l[fa[lca(x,y)]],-k);
ask(r[x])-ask(l[x]-1)
3.树链修改，子树和查询
设计同问题 $2$ ，接下来考虑节点 $x$ 的子树和：$\displaystyle \sum_{i=l[x]}^{r[x]}w[i](dep[i]+1)-dep[x]\sum_{i=l[x]}^{r[x]}w[i]$ 。对此，我们维护两个树状数组。(此处类比树状数组维护区间修改，区间查询)
add1(l[x],k*(dep[x]+1)),add1(l[y],k*(dep[y]+1)),add1(l[lca(x,y)],-k*(dep[lca(x,y)]+1)),add1(l[fa[lca(x,y)]],-k*(dep[fa[lca(x,y)]]+1)),
add2(l[x],k),add2(l[y],k),add2(l[lca(x,y)],-k),add2(l[fa[lca(x,y)]],k);
(ask1(r[x])-ask1(l[x]-1))-dep[x]*(ask2(r[x])-ask2(l[x]-1))
4.单点修改，树链和查询
对于树链和，我们尝试用树状数组直接维护节点到根的权值和，因此，单点修改就相当于差分修改。每次进行单点修改的时候，我们的差分影响只对其子树尝试贡献。所以，原问题相当于，区间修改，单点查询。
add(l[x],k),add(r[x]+1,-k);
ask(l[x]);
5.子树修改，树链和查询
对于树链和，我们依然是直接维护节点到根的权值和。不同于单点修改，子树修改的时候，对子树的影响会更大一点，具体的： 修改节点 $x$ 的子树，对子树内节点 $y$ 的影响为 $(dep[y]-dep[x]+1)*k$ ，依旧是拆分为两个树状数组。
add1(l[x],k),add1(r[x]+1,-k);
add2(l[x],k*(1-dep[x])),add2(r[x]+1,-k*(1-dep[y]));
ask1(l[x])*dep[x]-ask2(l[x]);
6.子树修改，单点查询
修改节点 $x$ 子树内权值，单点查询，相当于区间修改，单点查询。
add(l[x],k),add(r[x]+1,-k);
ask(l[x]);
7.子树修改，子树和查询
等价于区间修改，区间查询，即 $\displaystyle \sum_{i=1}^{r[x]}w_i(r[x]+1)-\sum_{i=1}^{r[x]}w_ii-(\sum_{i=1}^{l[x]-1}w_i(l[x]-1+1)-\sum_{i=1}^{l[x]-1}w_ii)$。同样是维护两个树状数组。
add1(l[x],k),add1(r[x]+1,-k);
add2(l[x],k*l[x]),add2(r[x],-k*r[x]);
ask1(r[x])*(r[x]+1)-ask2(r[x])-(ask1(l[x]-1)*(l[x]+1-1)-ask2(l[x]-1));