「Note」树论方向
1. 重鏈剖分
1.1. 簡介
重鏈剖分將樹分割成若干鏈維護信息，將樹的結(jié)構(gòu)轉(zhuǎn)換為線性結(jié)構(gòu)，然后可用其他數(shù)據(jù)結(jié)構(gòu)維護。
定義以下概念：
| 重子節(jié)點 | 輕子節(jié)點 | 重邊 | 輕邊 | 重鏈 |
|---|---|---|---|---|
| 某節(jié)點的子節(jié)點中子樹大小最大的那個 | 某節(jié)點的子節(jié)點中的非重子節(jié)點 | 由某節(jié)點到其重子節(jié)點的連邊 | 由某節(jié)點到其輕子節(jié)點的連邊 | 若干條頭尾相接的重邊構(gòu)成的鏈（落單的節(jié)點也看作一個重鏈） |
重鏈剖分有以下性質(zhì)：
- 剖分時優(yōu)先遍歷重邊，于是一條重鏈上的 DNF 序連續(xù)。
- 一顆子樹內(nèi) DFN 序連續(xù)。
根據(jù)這兩條性質(zhì)我們可以考慮維兩節(jié)點路徑上的信息，與一個子樹內(nèi)的信息。路徑上的信息可以用若干重鏈信息拼接而成維護，子樹內(nèi)則直接用一定范圍內(nèi)連續(xù) DFN 的節(jié)點信息維護即可。
重鏈剖分同時可以解決求 LCA 問題，當(dāng)然，這在維護路徑上信息時就需要用到。對于兩個節(jié)點，考慮將所在重鏈頂點深度大的節(jié)點跳轉(zhuǎn)至其所在重鏈頂點的父節(jié)點，進行此操作若干次直到兩者在一條重鏈上。最后一個一個跳轉(zhuǎn)即可。
1.2. 具體實現(xiàn)
實現(xiàn)時，維護以下變量：
| \(fa_i\) | \(dep_i\) | \(siz_i\) | \(hson_i\) | \(top_i\) | \(dfn_i\) | \(rk_i\) |
|---|---|---|---|---|---|---|
| 節(jié)點 \(i\) 的父節(jié)點 | 節(jié)點 \(i\) 的深度 | 節(jié)點 \(i\) 的子樹大小 | 節(jié)點 \(i\) 的重子節(jié)點 | 節(jié)點 \(i\) 所在重鏈頂點 | 節(jié)點 \(i\) 的 DFN 序 | DFN 序為 \(i\) 的節(jié)點編號 |
剖分操作需要進行兩次 DFS：
- 第一次 DFS 維護 \(fa_i,dep_i,siz_i,hson_i\)。
void DFS1(int now,int fa)
{
p[now].fa=fa,p[now].dep=p[fa].dep+1,p[now].siz=1,p[now].hson=0;
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==fa)
continue;
DFS1(to,now);
p[now].siz+=p[to].siz;
if(!p[now].hson||p[to].siz>p[p[now].hson].siz)
p[now].hson=to;
}
return;
}
- 第二次 DFS 維護 \(top_i,dfn_i,rk_i\)。
void DFS2(int now,int top)
{
p[now].top=top,p[now].dfn=++dcnt,rk[dcnt]=now;
if(p[now].hson)
DFS2(p[now].hson,top);
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==p[now].fa||to==p[now].hson)
continue;
DFS2(to,to);
}
return;
}
對于路徑維護，考慮在跳 LCA 的過程中每次跳轉(zhuǎn)維護跳轉(zhuǎn)路徑，直到兩節(jié)點跳至一條重鏈上，此時維護兩點間路徑即可。每次維護 \(dfn_y\to dfn_x\ （dep_x>dep_y）\)。
對于子樹維護，直接維護 \(dfn_x\to dfn_x+siz_x-1\) 即可。
1.3. 題目
\(\color{royalblue}{P3384}\)
重鏈剖分模板。
$\text{Code}$：
#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int MAXN=1e5+1,MAXM=2e5+1;
int n,m,R,Mod;
int pv[MAXN];
//----------//
//Edge
struct Edge
{
int to,nex;
}edge[MAXM];
int tot,head[MAXN];
void add(int from,int to)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
head[from]=tot;
return;
}
//--------------------//
const int MAXTN=4e5+1;
struct Seg_Tree
{
struct Seg_Tree_Node
{
int l,r;
LL val,lazy;
}t[MAXTN];
int seq[MAXN];
int ls(int rt){return rt<<1;}
int rs(int rt){return rt<<1|1;}
void tag(int rt,LL val)
{
t[rt].lazy+=val,t[rt].lazy%=Mod;
t[rt].val+=(t[rt].r-t[rt].l+1)*val%Mod,t[rt].val%=Mod;
return;
}
void push_up(int rt)
{
t[rt].val=(t[ls(rt)].val+t[rs(rt)].val)%Mod;
return;
}
void push_down(int rt)
{
if(!t[rt].lazy)
return;
tag(ls(rt),t[rt].lazy);
tag(rs(rt),t[rt].lazy);
t[rt].lazy=0;
return;
}
void build(int rt,int l,int r)
{
t[rt].l=l,t[rt].r=r,t[rt].lazy=0;
if(l==r)
{
t[rt].val=seq[l]%Mod;
return;
}
int mid=l+r>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
push_up(rt);
return;
}
void change(int rt,int l,int r,LL val)
{
if(t[rt].l>=l&&t[rt].r<=r)
{
tag(rt,val);
return;
}
push_down(rt);
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid)
change(ls(rt),l,r,val);
if(r>mid)
change(rs(rt),l,r,val);
push_up(rt);
return;
}
LL query(int rt,int l,int r)
{
if(t[rt].l>=l&&t[rt].r<=r)
return t[rt].val;
push_down(rt);
LL res=0;
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid)
res+=query(ls(rt),l,r),res%=Mod;
if(r>mid)
res+=query(rs(rt),l,r),res%=Mod;
return res;
}
}T;
//--------------------//
//DPH
struct Poi
{
int fa,dep,siz,hson;
int top,dfn;
}p[MAXN];
int dcnt,rk[MAXN];
void DFS1(int now,int fa)
{
p[now].fa=fa,p[now].dep=p[fa].dep+1,p[now].siz=1,p[now].hson=0;
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==fa)
continue;
DFS1(to,now);
p[now].siz+=p[to].siz;
if(!p[now].hson||p[to].siz>p[p[now].hson].siz)
p[now].hson=to;
}
return;
}
void DFS2(int now,int top)
{
p[now].top=top,p[now].dfn=++dcnt,rk[dcnt]=now;
if(p[now].hson)
DFS2(p[now].hson,top);
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==p[now].fa||to==p[now].hson)
continue;
DFS2(to,to);
}
return;
}
void init()
{
for(int i=1;i<=n;i++)
T.seq[p[i].dfn]=pv[i];
T.build(1,1,n);
return;
}
void changer(int x,LL val)
{
T.change(1,p[x].dfn,p[x].dfn+p[x].siz-1,val);
return;
}
LL queryr(int x)
{
return T.query(1,p[x].dfn,p[x].dfn+p[x].siz-1);
}
void changep(int x,int y,LL val)
{
while(p[x].top!=p[y].top)
{
if(p[p[x].top].dep<p[p[y].top].dep)
swap(x,y);
T.change(1,p[p[x].top].dfn,p[x].dfn,val);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep)
swap(x,y);
T.change(1,p[y].dfn,p[x].dfn,val);
return;
}
LL queryp(int x,int y)
{
LL res=0;
while(p[x].top!=p[y].top)
{
if(p[p[x].top].dep<p[p[y].top].dep)
swap(x,y);
res+=T.query(1,p[p[x].top].dfn,p[x].dfn),res%=Mod;
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep)
swap(x,y);
res+=T.query(1,p[y].dfn,p[x].dfn),res%=Mod;
return res;
}
//--------------------//
int main()
{
scanf("%d%d%d%d",&n,&m,&R,&Mod);
for(int i=1;i<=n;i++)
scanf("%d",&pv[i]);
for(int from,to,i=1;i<n;i++)
scanf("%d%d",&from,&to),add(from,to),add(to,from);
DFS1(R,0);
DFS2(R,R);
init();
LL val;
for(int op,x,y,i=1;i<=m;i++)
{
scanf("%d%d",&op,&x);
if(op==1)
{
scanf("%d%lld",&y,&val);
changep(x,y,val%Mod);
}
else if(op==2)
{
scanf("%d",&y);
printf("%lld\n",queryp(x,y));
}
else if(op==3)
{
scanf("%lld",&val);
changer(x,val%Mod);
}
else if(op==4)
printf("%lld\n",queryr(x));
}
return 0;
}
\(\color{blueviolet}{SP6779}\)
重鏈剖分，求路徑上最大子段和。
顯著地，線段樹維護以下信息：
- 區(qū)間和 \(sum\)。
- 區(qū)間最大子段和 \(mx\)。
- 區(qū)間左側(cè)最大子段和 \(lmx\)。
- 區(qū)間右側(cè)最大子段和 \(rmx\)。
合并時需要注意左右順序，尤其是在樹上合并鏈時。
$\text{Code}$：
#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=2e5+1,M=4e5+1;
int n,q;
//--------------------//
//Seg-Tree
const int TN=8e5+1;
struct Seg_Tree_Node
{
int l,r;
int sum,mx,lmx,rmx;
int lazy;
Seg_Tree_Node(){l=r=sum=mx=lmx=rmx=0,lazy=10001;}
};
struct Seg_Tree
{
Seg_Tree_Node t[TN];
int s[N];
int ls(int rt){return rt<<1;}
int rs(int rt){return rt<<1|1;}
void tag(int rt,int val)
{
t[rt].lazy=val;
t[rt].sum=(t[rt].r-t[rt].l+1)*val;
t[rt].mx=t[rt].lmx=t[rt].rmx=max(0,t[rt].sum);
return;
}
Seg_Tree_Node merge(Seg_Tree_Node x,Seg_Tree_Node y,int type)
{
if(!y.l)
swap(x,y);
if(!x.l)
{
if(type==1)
y.r-=y.l-1,y.l=1;
return y;
}
Seg_Tree_Node res;
res.sum=x.sum+y.sum;
res.lmx=max(x.lmx,x.sum+y.lmx);
res.rmx=max(y.rmx,y.sum+x.rmx);
res.mx=max(x.rmx+y.lmx,max(x.mx,y.mx));
if(type==1)
res.l=1,res.r=x.r+y.r-x.l-y.l+2;
else
res.l=x.l,res.r=y.r;
return res;
}
void push_down(int rt)
{
if(t[rt].lazy==10001)
return;
tag(ls(rt),t[rt].lazy),tag(rs(rt),t[rt].lazy);
t[rt].lazy=10001;
return;
}
void build(int rt,int l,int r)
{
t[rt].l=l,t[rt].r=r,t[rt].lazy=10001;
if(l==r)
{
t[rt].sum=s[l];
t[rt].mx=t[rt].lmx=t[rt].rmx=max(0,t[rt].sum);
return;
}
int mid=l+r>>1;
build(ls(rt),l,mid);
build(rs(rt),mid+1,r);
t[rt]=merge(t[ls(rt)],t[rs(rt)],0);
return;
}
void change(int rt,int l,int r,int val)
{
if(t[rt].l>=l&&t[rt].r<=r)
{
tag(rt,val);
return;
}
push_down(rt);
int mid=t[rt].l+t[rt].r>>1;
if(l<=mid)
change(ls(rt),l,r,val);
if(r>mid)
change(rs(rt),l,r,val);
t[rt]=merge(t[ls(rt)],t[rs(rt)],0);
return;
}
Seg_Tree_Node query(int rt,int l,int r)
{
if(t[rt].l>=l&&t[rt].r<=r)
return t[rt];
push_down(rt);
int mid=t[rt].l+t[rt].r>>1;
Seg_Tree_Node res;
if(l<=mid)
res=query(ls(rt),l,r);
if(r>mid)
res=merge(res,query(rs(rt),l,r),1);
t[rt]=merge(t[ls(rt)],t[rs(rt)],0);
return res;
}
}T;
//--------------------//
//Graph
struct Edge
{
int to,nex;
}edge[M];
int tot,head[N];
void add(int from,int to)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
head[from]=tot;
return;
}
struct Poi
{
int fa,dep,siz,hson;
int top,dfn;
int val;
}p[N];
int dcnt,rk[N];
void DFS1(int now,int fa)
{
p[now].fa=fa,p[now].dep=p[fa].dep+1,p[now].siz=1;
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==fa)
continue;
DFS1(to,now);
p[now].siz+=p[to].siz;
if(!p[now].hson||p[p[now].hson].siz<p[to].siz)
p[now].hson=to;
}
return;
}
void DFS2(int now,int top)
{
p[now].top=top,p[now].dfn=++dcnt,rk[dcnt]=now;
if(p[now].hson)
DFS2(p[now].hson,top);
for(int to,i=head[now];i;i=edge[i].nex)
{
to=edge[i].to;
if(to==p[now].hson||to==p[now].fa)
continue;
DFS2(to,to);
}
return;
}
void init()
{
DFS1(1,0);
DFS2(1,1);
for(int i=1;i<=n;i++)
T.s[p[i].dfn]=p[i].val;
T.build(1,1,n);
return;
}
void change(int x,int y,int val)
{
while(p[x].top!=p[y].top)
{
if(p[p[x].top].dep<p[p[y].top].dep)
swap(x,y);
T.change(1,p[p[x].top].dfn,p[x].dfn,val);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep)
swap(x,y);
T.change(1,p[y].dfn,p[x].dfn,val);
return;
}
int query(int x,int y)
{
Seg_Tree_Node resx,resy;
while(p[x].top!=p[y].top)
{
if(p[p[x].top].dep<p[p[y].top].dep)
swap(x,y),swap(resx,resy);
resx=T.merge(T.query(1,p[p[x].top].dfn,p[x].dfn),resx,1);
x=p[p[x].top].fa;
}
if(p[x].dep<p[y].dep)
swap(x,y),swap(resx,resy);
resx=T.merge(T.query(1,p[y].dfn,p[x].dfn),resx,1);
swap(resx.lmx,resx.rmx);
resx=T.merge(resx,resy,1);
return resx.mx;
}
//--------------------//
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i].val);
for(int from,to,i=1;i<n;i++)
scanf("%d%d",&from,&to),add(from,to),add(to,from);
init();
scanf("%d",&q);
for(int op,x,y,z,i=1;i<=q;i++)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
printf("%d\n",query(x,y));
else
{
scanf("%d",&z);
change(x,y,z);
}
}
return 0;
}
\(\color{blueviolet}{P2486}\)
路徑上顏色段數(shù)，維護信息與上題類似，注意合并細節(jié)。
2. 點分治
2.1. 靜態(tài)點分治
適用于離線處理樹上路徑問題。
任選一個根，任意一條路徑都只有兩種狀態(tài)：完全在此點某子節(jié)點子樹內(nèi)、經(jīng)過根并兩端在其子節(jié)點子樹內(nèi)（或端點為根）。
對于每一個路徑，我們考慮其端點 LCA 節(jié)點統(tǒng)計其貢獻。所以可以考慮每次找一個點統(tǒng)計其貢獻，并把其刪掉，統(tǒng)計剩余森林貢獻，以此類推。
但這樣復(fù)雜度仍然不夠優(yōu)秀，我們可以每次選擇重心進行分治，這樣就可以做到 \(O(n \log n)\) 分治。
具體地，對于當(dāng)前子樹，我們找出其重心作為根，統(tǒng)計其各個子樹信息進行合并與統(tǒng)計（不能經(jīng)過打標記即刪除了的節(jié)點），然后再處理其各個子節(jié)點子樹，求解子問題。
特別地，每次尋找重心之后需要更新各個節(jié)點子樹大小，否則復(fù)雜度會有問題。
需要注意的是每次找重心都需要更新當(dāng)前處理的子樹大小，否則復(fù)雜度仍然不對。
2.2. 動態(tài)點分治
考慮如果有多次詢問，如果每次都進行靜態(tài)點分治那么復(fù)雜度我們將不能接受。而多次詢問其中分治過程都相同，有大量重復(fù)計算。于是我們可以記錄分治樹，其形態(tài)固定，將每一層分治重心與上一層的相連，得到一顆重構(gòu)樹，我們稱為點分樹。
點分樹的性質(zhì)：
- 它是一棵有根樹。
- 樹深最多是 \(O(\log n)\) 級別的。
- 樹上每個節(jié)點度數(shù)不大于其在原樹上的度數(shù) \(+ 1\)，
- 對于 \(u, v\) 兩點，其點分樹上的 LCA 一定在原樹的兩點間路徑上。
- 設(shè) \(siz_u\) 表示 \(u\) 節(jié)點在點分樹上的子樹大小，有 \(\sum \limits_{u \in T} siz_u\) 是 \(O(n \log n)\) 級別的。
- 點分樹上，節(jié)點 \(u\) 的子節(jié)點 \(v\) 的子樹中與原樹中對應(yīng)的節(jié)點 \(u\) 子節(jié)點子樹的點編號相同，樹的形態(tài)不一定相同。
與點分治類似的，動態(tài)點分治也用于解決路徑問題；不同的是動態(tài)點分治一般是多次查詢，每次固定一個端點。
考慮一個點在分治過程中被計入貢獻，當(dāng)且僅當(dāng)分治中心是其點分樹上祖先或者是其本身。所以處理一個點的詢問時從其本身出發(fā)，枚舉其祖先作為此點與其他點的 LCA 進行處理。
特別地，處理當(dāng)前點貢獻時，可能會處理到與父節(jié)點重復(fù)的貢獻，此時用類似容斥的方式減去貢獻即可。總之處理點分樹某點子樹內(nèi)貢獻時需要減去不合法貢獻。
接下來以模板題舉例。
給定一棵樹，每個點有點權(quán)。\(q\) 次詢問給定 \(x, k\)，求樹上距離不超過 \(k\) 的所有點的點權(quán)和。帶修點權(quán)，強制在線。\(n, q \le 10 ^ 5\)。
考慮建出點分樹，并按上述方式枚舉 LCA（分治點）。設(shè) \(fa_u\) 表示節(jié)點 \(u\) 在點分樹上的父節(jié)點，\(dis(u, v)\) 表示 \(u, v\) 兩點在原樹上的距離。\(dis(u, v)\) 可以 \(O(1)\) 求，只要預(yù)處理深度以及 ST 表求 LCA 即可。
初始我們在節(jié)點 \(x\) 上，令答案累加 \(\sum \limits_{dis(u, x) \le k} val_u\)，然后令跳至 \(fa_x\)，累計答案 \(\sum \limits_{dis(u, fa_x) \le k - dis(x, fa_x)} val_u\)。此時我們發(fā)現(xiàn)在記錄 \(fa_x\) 的貢獻過程中多計算了在 \(x\) 子樹內(nèi)的信息，所以令答案減去 \(\sum \limits_{u \in T_x \land dis(u, fa_x) \le k - dis(x, fa_x)} val_u\)，以此類推。
所以我們對于一個節(jié)點 \(u\) 來說需要維護子樹內(nèi)與 \(u\) 節(jié)點不超過某一距離的權(quán)值和、子樹內(nèi)與 \(fa_u\) 節(jié)點不超過某一距離的權(quán)值和。這個東西可以用樹狀數(shù)組或者動態(tài)開點線段樹解決，注意空間配置即可。
修改某一點顯著只會影響點分樹一條鏈上的點，暴力枚舉修改即可。
2.3. 題目
\(\color{royalblue}{P3806}\)
靜態(tài)點分治模板題，在分治過程中處理多組詢問以減少常數(shù)。
類似于樹形 DP，對于一次分治，處理當(dāng)前正在遍歷的子樹信息，并且合并到當(dāng)前樹上來，以此類推。
特別地，計算結(jié)束需要反向撤銷影響來進行下一步操作
$\text{Code}$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UIT;
typedef double DB;
//--------------------//
const int N = 1e4 + 5, Q = 100 + 5, M = 2e4 + 5, K = 1e7 + 5;
int n, m, q[Q];
bool ans[Q];
struct Edge {
int to, w, nex;
} edge[M];
int tot, head[N];
void add(int from, int to, int w) {
edge[++tot] = {to, w, head[from]};
head[from] = tot;
}
int stot, siz[N], mxsiz[N];
bool vis[N];
int rt, val;
void find_g(int now, int fa) {
mxsiz[now] = siz[now] = 1;
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != fa && !vis[to])
find_g(to, now), siz[now] += siz[to], mxsiz[now] = max(mxsiz[now], siz[to]);
}
mxsiz[now] = max(mxsiz[now], stot - siz[now]);
if (rt && mxsiz[now] == val)
rt = min(rt, now);
if (!rt || mxsiz[now] < val)
rt = now, val = mxsiz[now];
}
int tcnt, tem[N], dep[N];
void calc(int now, int fa) {
tem[++tcnt] = dep[now];
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != fa && !vis[to])
dep[to] = dep[now] + edge[i].w, calc(to, now);
}
}
int rcnt, rec[N];
bool dis[K];
void divide(int now) {
dis[0] = true, rec[++rcnt] = 0;
vis[now] = true;
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (vis[to])
continue;
tcnt = 0, dep[to] = edge[i].w;
calc(to, now);
for (int j = 1; j <= m; j++)
for (int k = 1; k <= tcnt && !ans[j]; k++)
if (q[j] >= tem[k])
ans[j] |= dis[q[j] - tem[k]];
for (int j = 1; j <= tcnt; j++)
if (tem[j] <= 1e7)
dis[tem[j]] = true, rec[++rcnt] = tem[j];
}
while (rcnt)
dis[rec[rcnt]] = false, rcnt--;
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (vis[to])
continue;
stot = siz[to], rt = 0, val = 0;
find_g(to, 0);
int temp = rt, tempv = val;
find_g(rt, 0);
// if (rt != temp)
// printf("%d %d %d %d %d %d\n", temp, rt, mxsiz[temp], mxsiz[rt], stot, tempv), exit(0);
divide(rt);
}
}
//--------------------//
int main() {
// double t1 = clock();
scanf("%d%d", &n, &m);
for (int u, v, w, i = 1; i < n; i++)
scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w);
for (int i = 1; i <= m; i++)
scanf("%d", &q[i]);
stot = n;
find_g(1, 0);
int temp = rt;
find_g(rt, 0);
// if (temp != rt)
// printf("fuck"), exit(0);
divide(rt);
for (int i = 1; i <= m; i++)
puts(ans[i] ? "AYE" : "NAY");
// printf("%.0lfms", clock() - t1);
return 0;
}
\(\color{blueviolet}{P4178}\)
靜態(tài)點分治，與其模板不同的是要求不超過 \(k\) 的路徑數(shù)，拿樹狀數(shù)組維護即可。
\(\color{blueviolet}{P4149}\)
靜態(tài)點分治，類似地，對于一定長度的路徑，取邊數(shù)量最小值即可。
\(\color{black}{P2664}\)
靜態(tài)點分治。
考慮顏色對端點的貢獻，首先特殊化根的答案以及貢獻，這部分是簡單的，然后考慮子樹內(nèi)節(jié)點的答案以及貢獻。
設(shè) \(f_x\) 表示節(jié)點 \(x\) 的貢獻，對于一個節(jié)點 \(x\)，若其祖先節(jié)點中沒有和其同色的，有 \(f_x = siz_x\)，否則 \(f_x = 0\)。
對于某點 \(x\)，考慮一條 \(x\) 到 \(y\) 的路徑，將其分為 \(x \to \mathrm{root}\) 以及 \(\mathrm{root} \to y\) 兩部分分別考慮貢獻。
對于前者，考慮此部分的每個顏色，都會在 \(y\) 取到不同的點的時候造成一次貢獻，所以每個顏色會產(chǎn)生 \(siz_{\mathrm{root}} - siz_{\mathrm{branch}}\) 的貢獻，其中 \(\mathrm{branch}\) 表示 \(x\) 所在的子樹。
對于后者，考慮每個節(jié)點都會造成一次貢獻，所以有貢獻 \(\sum \limits _ {y \notin \mathrm{branch}} f_y\)。
考慮兩部分貢獻可能多算，因為顏色可能有重復(fù)，也就是說統(tǒng)計 \(\mathrm{root} \to y\) 部分貢獻時只能累加不在 \(x \to \mathrm{root}\) 路徑上的顏色的貢獻，我們選擇額外減去其貢獻。
對于一個點 \(x\)，一次計算中有其答案（設(shè) \(x \to \mathrm{root}\) 路徑上的顏色集合為 \(C\)）：
\]
其中 \(\sum \limits _ {y \notin \mathrm{branch}} f_y = \sum \limits_{i \in T_{\mathrm{root}}} f_i - \sum \limits_{i \in mathrm{branch}} f_i\)，然后寫巨大多 DFS 就可以解決了。
\(\color{blueviolet}{P6329}\)
動態(tài)點分治模板。
$\text{Code}$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UIT;
typedef double DB;
//--------------------//
const int N = 1e5 + 5, M = 4e5 + 5;
int n, m, pv[N];
struct Edge {
int to, nex;
} edge[M];
int tot, head1[N], head2[N];
void add(int from, int to, int *head) {
edge[++tot] = {to, head[from]};
head[from] = tot;
}
int root, rt, rsiz;
int stot, siz[N], mxsiz[N];
bool vis[N];
void calc_g(int now, int fa) {
siz[now] = 1, mxsiz[now] = 0;
for (int to, i = head1[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != fa && !vis[to])
calc_g(to, now), siz[now] += siz[to], mxsiz[now] = max(mxsiz[now], siz[to]);
}
mxsiz[now] = max(mxsiz[now], stot - siz[now]);
if (rt && mxsiz[now] == rsiz)
rt = min(rt, now);
if (!rt || mxsiz[now] < rsiz)
rt = now, rsiz = mxsiz[now];
}
void divide(int now) {
vis[now] = true;
for (int to, i = head1[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (vis[to])
continue;
rt = rsiz = 0, stot = siz[to];
calc_g(to, 0);
calc_g(rt, 0);
add(now, rt, head2), add(rt, now, head2);
// printf("%d %d\n", now, rt);
divide(rt);
}
}
const int LG = 17 + 5;
int dcnt, dfn[N], dep[N];
int get(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
struct ST {
int val[LG][N];
void init() {
int mxl = __lg(n);
for (int i = 1; i <= mxl; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
val[i][j] = get(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
}
int query(int u, int v) {
if (u == v)
return u;
if ((u = dfn[u]) > (v = dfn[v]))
swap(u, v);
int lgl = __lg(v - u++);
return get(val[lgl][u], val[lgl][v - (1 << lgl) + 1]);
}
} S;
void DFS(int now, int fa) {
dfn[now] = ++dcnt, S.val[0][dfn[now]] = fa;
for (int to, i = head1[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != fa)
dep[to] = dep[now] + 1, DFS(to, now);
}
}
#define lobit(x) ((x) & (-(x)))
struct BIT {
int mxv;
vector<int> sum;
void init() {
sum.resize(mxv + 1);
}
void change(int pos, int val) {
while (pos <= mxv)
sum[pos] += val, pos += lobit(pos);
}
int query(int pos) {
if (pos <= 0)
return 0;
int res = 0; pos = min(pos, mxv);
while (pos)
res += sum[pos], pos -= lobit(pos);
return res;
}
} T[N][2];
int f[N];
void build(int now, int fa) {
T[now][0].mxv = 1, f[now] = fa;
for (int to, i = head2[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != fa)
build(to, now), T[now][0].mxv += T[to][0].mxv;
}
T[now][0].init();
T[now][1].mxv = T[now][0].mxv + 1;
T[now][1].init();
}
int dis(int u, int v) {
int lca = S.query(u, v);
return dep[u] + dep[v] - 2 * dep[lca];
}
void change(int now, int val) {
int pos = now;
while (pos != root) {
T[pos][0].change(dis(now, pos) + 1, val - pv[now]), T[pos][1].change(dis(now, f[pos]) + 1, val - pv[now]);
// printf("c %d %d %d\n", now, pos, val - pv[now]);
pos = f[pos];
}
T[root][0].change(dis(now, root) + 1, val - pv[now]);
pv[now] = val;
}
int query(int now, int val) {
int res = 0, pos = now;
while (pos != root) {
res += T[pos][0].query(val - dis(now, pos) + 1) - T[pos][1].query(val - dis(now, f[pos]) + 1);
// printf("pos %d %d %d\n", pos, res, val);
pos = f[pos];
}
res += T[root][0].query(val - dis(now, root) + 1);
return res;
}
//--------------------//
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &pv[i]);
for (int u, v, i = 1; i < n; i++)
scanf("%d%d", &u, &v), add(u, v, head1), add(v, u, head1);
DFS(1, 0), S.init();
stot = n;
calc_g(1, 0);
calc_g(rt, 0);
// puts("");
divide(root = rt);
// printf("root : %d\n", root);
build(root, 0);
for (int tem, i = 1; i <= n; i++)
tem = pv[i], pv[i] = 0, change(i, tem);
int las = 0;
for (int op, x, y, i = 1; i <= m; i++) {
scanf("%d%d%d", &op, &x, &y);
x ^= las, y ^= las;
if (op == 0)
printf("%d\n", las = query(x, y));
else
change(x, y);
}
return 0;
}
\(\color{blueviolet}{P3345}\)
（此部分抄自 Alex_Wei 博客。）
如果一個節(jié)點的某個子節(jié)點子樹內(nèi)權(quán)值和大于剩余部分，那么此節(jié)點的這個子節(jié)點比此節(jié)點更優(yōu)。相當(dāng)于求樹上帶權(quán)重心。
建出點分樹暴力找出更優(yōu)的節(jié)點，考慮對一個節(jié)點 \(u\) 求 \(f(u) = \sum\limits_v d_v \times dis(u, v)\)，維護 \(s_{0, u}\) 表示 \(u\) 的點分樹子樹 \(T_u\) 的 \(\sum\limits_{v\in T_u} d_v \times dis(u, v)\)，\(s_{1, u}\) 表示 \(\sum\limits_{v\in T_u} d_v\times dis(fa_u, v)\)，\(c_u\) 表示 \(\sum \limits_{v \in T_u} d_v\) 則有：
\]
注意，從父節(jié)點 \(x\) 移動到子節(jié)點 \(u\) 時，記路徑 \(x \to u\) 上第一個節(jié)點為 \(suc_u\)，那么 \(suc_u\) 的子樹大小 \(c_{suc_u}\) 需要增加 \(c_u - c_{suc_u}\)。注意修改需要作用于點分樹 \(suc_u \to x\) 路徑上除了 \(x\) 以外的所有節(jié)點。回溯時清空修改。
\(\color{blueviolet}{P3241}\)
先建點分樹，對于點 \(u\) 維護一下子樹內(nèi)所有點權(quán)及其 \(dis(x, u)\)、\(dis(x, fa_u)\)，將他們按照點權(quán)排序，每次二分可求貢獻區(qū)間，前綴和求貢獻。
但是這樣會有 \(2\) 倍常數(shù)，于是我們利用每個點度數(shù)不超過 \(3\) 的性質(zhì)進行優(yōu)化。考慮去掉我們當(dāng)前子樹的貢獻等價于只取當(dāng)前父節(jié)點其他子節(jié)點子樹貢獻，所以從父親方面求一下其他子節(jié)點子樹貢獻即可，這樣只用維護一個 vector。
3. 長鏈剖分
3.1. 簡介
與重鏈剖分除了重子節(jié)點的選擇不同外，剩下的剖分部分都是相同的。
定義節(jié)點 \(i\) 子樹深度為節(jié)點 \(i\) 距離其子樹內(nèi)最深的葉子節(jié)點的距離。
節(jié)點 \(i\)? 的重子節(jié)點即所有子節(jié)點中子樹深度最大的那個。
至于實現(xiàn)可以參考重鏈剖分，一般來講不需要在鏈上維護信息，所以不用記錄 dfs 序。
需要記錄一個子樹深度 \(mxd\)，初始化葉子節(jié)點 \(mxd \leftarrow 0/1\) 至于是 \(0\) 是 \(1\) 則根據(jù)維護邊和點來判斷即可。
3.2. 性質(zhì)與應(yīng)用
性質(zhì)（都很顯然）：
- 當(dāng)前節(jié)點所在長鏈末端節(jié)點即當(dāng)前節(jié)點子樹內(nèi)最深的節(jié)點（顯然是一個葉子節(jié)點）。
- 從根節(jié)點跳到任意一個節(jié)點經(jīng)過長鏈的數(shù)量（等價于輕邊數(shù)量）不超過 \(\sqrt n\)。
- 一個節(jié)點的 \(k\) 級祖先所在長鏈長度不小于 \(k\)。
- 所有長鏈點數(shù)總和為 \(n\)。
3.2.1. 樹上 \(k\) 級祖先
預(yù)處理每個長鏈頂向上向下跳不超過鏈長的所有節(jié)點，這些信息是 \(O(n)\) 級的，再預(yù)處理每個節(jié)點的倍增跳祖先，復(fù)雜度 \(O(n \log n)\)。
還要預(yù)處理每個數(shù)的二進制下最高位，即 \(\log_2 x\)。
對于一個節(jié)點 \(u\)，要求其 \(k\) 級祖先，先跳至其 \(2^{\log_2 k}\) 級祖先，根據(jù)性質(zhì)的第三條可以確定當(dāng)前鏈鏈頂可以通過向上向下跳不超過長鏈長度到達目標點，根據(jù)深度計算然后直接跳轉(zhuǎn)即可。
復(fù)雜度 \(O(n\log n) - O(1)\)，常數(shù)稍大。
3.2.2. 優(yōu)化 DP
一般來講長鏈優(yōu)化 DP 都需要以相對深度為下標，這樣子節(jié)點信息可以通過下標平移 \(1\) 來傳到父節(jié)點。參考樹上啟發(fā)式合并，先繼承重子節(jié)點信息，再將其他子節(jié)點的鏈信息暴力合并，每個節(jié)點合并一次，總次數(shù)是 \(O(n)\) 級別的。
以 \(\color{blueviolet}{CF1009F}\) 為例。
設(shè) \(f_{i, j}\) 表示節(jié)點 \(i\) 子樹內(nèi)距 \(i\) 距離為 \(j\) 的節(jié)點個數(shù)。
時間復(fù)雜度為 \(O(n^2)\)，無法接受。
考慮只有一條鏈的情況，設(shè)節(jié)點 \(u\) 的子節(jié)點為 \(v\)。
可以得到 \(f_{u, i} = f_{u, i - 1}, f_{u, 0} = 1\)。
也就是說當(dāng)前節(jié)點信息可以直接繼承子節(jié)點信息，但是要處理下標偏移。
想象我們有一個 \(val\) 數(shù)組 \(val_i\) 表示這條鏈上深度為 \(i\) 的節(jié)點個數(shù)（因為是鏈顯然為 \(1\)），我們可以將 \(f_u\) 作為指針指向其位置設(shè)為 \(val_p\)，則 \(f_v\) 指向 \(val_{p + 1}\)。
我們將所有長鏈進行以上操作，對于每個長鏈分配一個空間進行 DP，合并兩條鏈直接暴力即可，每次將當(dāng)前節(jié)點所有兒子合并到當(dāng)前長鏈上，以此類推。每個節(jié)點會被合并一次，復(fù)雜度是優(yōu)秀的 \(O(n)\)?，實現(xiàn)較為巧妙，可以看下文題目的代碼。
3.3. 題目
\(\color{royalblue}{P5903}\)
樹上 \(k\) 級祖先模板，長鏈剖分。
$\text{Code}$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UIT;
typedef double DB;
typedef pair<int, int> PII;
#define fi first
#define se second
//--------------------//
const int N = 5e5 + 5;
int n, m, root;
UIT s;
inline UIT get(UIT x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return s = x;
}
//----------//
// Graph
struct Edge {
int to, nex;
} edge[N];
int tot, head[N];
void add(int from, int to) {
edge[++tot] = {to, head[from]};
head[from] = tot;
// printf("%d %d\n", from, to);
}
//--------------------//
// LPD
const int LG = 18 + 5;
struct Poi {
int fa[LG], dep, mxd, hson, top;
vector<int> up, dw;
} p[N];
int lg[N], pw2[LG];
void lg_init() {
for (int i = 2; i <= n; i++)
lg[i] = lg[i >> 1] + 1;
for (int i = pw2[0] = 1; i <= lg[n]; i++)
pw2[i] = pw2[i - 1] << 1;
}
void DFS1(int now, int fa) {
p[now].fa[0] = fa, p[now].mxd = 1, p[now].dep = p[fa].dep + 1;
// printf("now %d %d\n", now, p[now].dep);
for (int i = 1; i <= lg[p[now].dep]; i++)
p[now].fa[i] = p[p[now].fa[i - 1]].fa[i - 1];
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
DFS1(to, now);
p[now].mxd = max(p[now].mxd, p[to].mxd + 1);
if (!p[now].hson || p[to].mxd > p[p[now].hson].mxd)
p[now].hson = to;
}
}
void DFS2(int now, int top) {
if (now == top) {
p[now].up.resize(p[now].mxd), p[now].dw.resize(p[now].mxd);
for (int j = 0, i = now; i && j < p[now].mxd; i = p[i].fa[0], j++)
p[now].up[j] = i;
}
// printf("top %d %d\n", now, p[now].dep - p[top].dep);
p[top].dw[p[now].dep - p[top].dep] = now, p[now].top = top;
if (p[now].hson)
DFS2(p[now].hson, top);
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to != p[now].hson)
DFS2(to, to);
}
}
int get_kfa(int now, int k) {
if (k == 0)
return now;
now = p[now].fa[lg[k]];
k -= pw2[lg[k]] + (p[now].dep - p[p[now].top].dep), now = p[now].top;
if (k >= 0)
return p[now].up[k];
return p[now].dw[-k];
}
//--------------------//
int main() {
// freopen("P5903_1.in", "r", stdin);
scanf("%d%d%u", &n, &m, &s);
LL ans = 0; int lst = 0;
for (int x, i = 1; i <= n; i++) {
scanf("%d", &x);
if (x)
add(x, i);
else
root = i;
}
lg_init(), DFS1(root, 0), DFS2(root, root);
for (int x, k, i = 1; i <= m; i++) {
x = ((get(s) ^ lst) % n) + 1, k = (get(s) ^ lst) % p[x].dep;
ans ^= 1LL * i * (lst = get_kfa(x, k));
// printf("ans %d %d %d\n", x, k, lst);
}
printf("%lld", ans);
return 0;
}
\(\color{blueviolet}{CF1009F}\)
長鏈剖分優(yōu)化 DP 板子，每次繼承重子節(jié)點信息，指針處理下下標平移，剩余節(jié)點暴力合并，復(fù)雜度線性。
$\text{Code}$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UIT;
typedef double DB;
typedef pair<int, int> PII;
#define fi first
#define se second
//--------------------//
const int N = 1e6 + 5, N2 = 2e6 + 5;
int n, mxv[N], ans[N];
struct Edge {
int to, nex;
} edge[N2];
int tot, head[N];
void add(int from, int to) {
edge[++tot] = {to, head[from]};
head[from] = tot;
}
//--------------------//
int cur, val[N], *f[N];
struct Poi {
int fa, dep, mxd, hson;
} p[N];
void DFS1(int now, int fa) {
p[now].fa = fa, p[now].dep = p[fa].dep + 1;
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to == fa)
continue;
DFS1(to, now);
p[now].mxd = max(p[now].mxd, p[to].mxd + 1);
if (!p[now].hson || p[p[now].hson].mxd < p[to].mxd)
p[now].hson = to;
}
}
void DFS2(int now) {
f[now][0] = 1, mxv[now] = 1, ans[now] = 0;
if (p[now].hson) {
f[p[now].hson] = f[now] + 1, DFS2(p[now].hson);
if (mxv[p[now].hson] > mxv[now])
mxv[now] = mxv[p[now].hson], ans[now] = ans[p[now].hson] + 1;
}
for (int to, i = head[now]; i; i = edge[i].nex) {
to = edge[i].to;
if (to == p[now].fa || to == p[now].hson)
continue;
f[to] = val + cur, cur += p[to].mxd + 1, DFS2(to);
for (int i = 0; i <= p[to].mxd; i++) {
f[now][i + 1] += f[to][i];
if (f[now][i + 1] > mxv[now] || (f[now][i + 1] == mxv[now] && i + 1 < ans[now]))
mxv[now] = f[now][i + 1], ans[now] = i + 1;
}
}
}
//--------------------//
int main() {
scanf("%d", &n);
for (int u, v, i = 1; i < n; i++)
scanf("%d%d", &u, &v), add(u, v), add(v, u);
DFS1(1, 0);
f[1] = val, cur += p[1].mxd + 1;
DFS2(1);
for (int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}
\(\color{blueviolet}{P5904}\)
長鏈剖分優(yōu)化 DP。
設(shè) \(f_{i, j}\) 表示節(jié)點 \(i\) 字數(shù)內(nèi)距 \(i\) 距離為 \(j\) 的點的個數(shù)。
設(shè) \(g_{i, j}\) 表示滿足一下條件的無序點對 \((x, y)\) 個數(shù)，\(i\) 子樹外若存在距 \(i\) 距離為 \(j\) 的節(jié)點 \(z\)，則 \((x, y, z)\) 是一組合法三元組。
邊轉(zhuǎn)移邊統(tǒng)計答案，簡單乘法原理處理即可。
\(\color{blueviolet}{P3441}\)
長鏈剖分優(yōu)化貪心。
顯著的，直徑肯定要選，然后每次選的時候肯定跨直徑最優(yōu)，如果存在兩對不跨直徑的點對，顯然可以轉(zhuǎn)換為兩個跨直徑的點對。
把直徑一端拎起來當(dāng)根節(jié)點，然后取最長的 \(2m - 1\) 個長鏈即可。（因為發(fā)現(xiàn)上文說的那個東西和取葉子節(jié)點覆蓋是等價的。）
總結(jié)
以上是生活随笔為你收集整理的「Note」树论方向的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： sqlite:No module nam
- 下一篇： pe下怎么删除软件 Pe系统如何卸载软件