靜態(tài) top tree 入門

理論

我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)維護(hù)樹上的問題，仿照序列上的問題，我們需要一個(gè)方法快速的刻畫出信息。

比如說線段樹就通過分治的方式來通過將一個(gè)區(qū)間劃分成 \(\log n\) 個(gè)區(qū)間并刻畫出這 \(\log n\) 個(gè)區(qū)間的信息。

然后我們考慮把這個(gè)東西放到樹上類比。你發(fā)現(xiàn)線段樹上每個(gè)非葉節(jié)點(diǎn)都有兩個(gè)兒子，那么你劃分樹上信息的方式應(yīng)當(dāng)也滿足這個(gè)性質(zhì)，也就是說把樹劃分成聯(lián)通子圖的過程中，應(yīng)當(dāng)每次合并兩個(gè)聯(lián)通子圖，同時(shí)線段樹只有兩個(gè)端點(diǎn)（維護(hù)的是區(qū)間）所以這個(gè)聯(lián)通子圖應(yīng)當(dāng)只有兩個(gè)界點(diǎn)（與其他聯(lián)通子圖公用的點(diǎn)，這里認(rèn)為維護(hù)的是邊集信息，聯(lián)通子圖間邊集不交）。

接下來我們把一個(gè)劃分出的聯(lián)通子圖稱為簇。初始每條邊都是一個(gè)簇。在合并簇的過程中合并出新的簇也會以一條邊的形式出現(xiàn)在樹上用于下一次合并。

合并兩個(gè)簇

分為兩種。

compress

我們將一個(gè)二度點(diǎn)縮掉，或者說將對于兩條相鄰的邊，若他們的公共點(diǎn)度數(shù)為 \(2\) 那么就把這兩條邊合并。合并出的新簇包含原來兩個(gè)簇的邊集，我們記這樣的點(diǎn)是 C 點(diǎn)。

rake

對于一個(gè)度數(shù)為 \(1\) 的點(diǎn) \(u\)，其唯一的邊為 \((u,v)\) 我們將 \((u,v)\) 這條邊代表的簇與點(diǎn) \(v\) 任意一個(gè)其他的邊代表的簇合并。

最后不難發(fā)現(xiàn)的是只會剩下一條邊。而合并的過程建出一棵樹就是 Top tree。

靜態(tài)構(gòu)建

實(shí)際上根據(jù)全局平衡二叉樹的建法可以給出一個(gè) \(2 \times \log n\) 樹高的構(gòu)建方法。

首先按全局平衡二叉樹的方法對原樹劃分，然后輕兒子先把所有簇收縮后 rake 到虛父親上，對于一條輕兒子全部 rake 完成的重鏈再用全局平衡二叉樹對重鏈的劃分方式把重鏈上所有邊 compress 成一條然后向上遞歸。

不過對于有多個(gè)輕兒子的點(diǎn)顯然是有問題的。所以對于多個(gè)輕兒子在按照重量選取帶權(quán)中點(diǎn)，每次按照中點(diǎn)分治，兩個(gè)分治區(qū)間內(nèi)的輕兒子 rake 成一條在 rake 到一起，還是重量平衡的，所以樹高 \(2 \times \log n\)。

按照這種方法建樹，需要 \(2\) 倍空間。

維護(hù)點(diǎn)信息

對于每個(gè)簇我們維護(hù)的信息不包括界點(diǎn)信息，在合并信息的時(shí)候再把刪除的界點(diǎn)的信息帶上，那么你發(fā)現(xiàn)修改點(diǎn)只需要在他被刪掉的簇時(shí)修改在一路爬上去就行了，時(shí)間復(fù)雜度是 \(O(\log n)\)。

應(yīng)用

動態(tài) dp

維護(hù)矩陣（線性變換）

ABC351G

對于一個(gè)聯(lián)通子圖來說，若其中只有一個(gè)葉子的值不確定，我們可以把這個(gè)聯(lián)通子圖的根的 dp 值寫成關(guān)于不確定葉子的值的線性變換形式，對于這道題目而言就是 \(y = k \times x + b\) 的一次函數(shù)形式。

更進(jìn)一步地化簡，因?yàn)?\(dp_{u} = a_{u} + \prod dp_v\)，而 \(a_u\) 是一個(gè)很簡單的項(xiàng)，所以不妨對于每個(gè)聯(lián)通子圖表示出 \(\prod dp_v = k \times dp_{x} + b\) 這里 \(x\) 表示聯(lián)通子圖中尚未確定的那個(gè)點(diǎn)的 \(dp\) 值。

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
const int mod = 998244353;
//#define lowbit(x) (x&(-x))
using namespace std;
namespace IO{
    const int SIZE=1<<21;
    static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
    #define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
    #define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
    #define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
    #define puts(x) IO::Puts(x)
    template<typename T>
    inline void read(T&x){
        for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
        for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15);
        x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
        for(int i=0;s[i];++i)
            putchar(s[i]);
        putchar('\n');
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
const int maxn = 4e5+114;
struct node{
	int u,v,id;
	int k,b;
	char type;
	//u 在上面 v 在下面
}cluster[maxn];
int n,m,a[maxn];
int pos[maxn],fa[maxn],ls[maxn],rs[maxn];
char type[maxn];//P 是邊點(diǎn) C 是 compress 點(diǎn) R 是 rake 點(diǎn)
int root=1;//根簇
void compress(node x,node y,node &w){
	//x 在上面 y 在下面
	w.u=x.u;
	w.v=y.v;
	w.k=1ll*x.k*y.k%mod;
	w.b=(1ll*x.k*y.b%mod+1ll*x.k*a[x.v]%mod+x.b)%mod;
	pos[x.v]=w.id;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	//cout<<"compress"<<w.u<<" "<<w.v<<" "<<w.ans<<'\n';
	w.type='C';
	root=w.id;
}
void rake(node x,node y,node &w){
	//把 x rake 到 y 上
	w.u=x.u;
	w.v=y.v;
	w.k=1ll*y.k*(1ll*x.k*a[x.v]%mod+x.b)%mod;
	w.b=1ll*y.b*(1ll*x.k*a[x.v]%mod+x.b)%mod;
	pos[x.v]=w.id;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	//cout<<"rake"<<w.u<<' '<<w.v<<' '<<w.ans<<'\n';
	w.type='R';
	root=w.id;
}
void update(int u){
    if(u==0) return ;
    if(cluster[u].type=='C'){
        compress(cluster[ls[u]],cluster[rs[u]],cluster[u]);
        update(fa[u]);
    }else{
        rake(cluster[ls[u]],cluster[rs[u]],cluster[u]);
        update(fa[u]);
    }
}
vector<int> E[maxn];
int father_pos[maxn];//一個(gè)點(diǎn)到其父親的邊的簇編號
int father[maxn];
int son[maxn],sz[maxn],tot;
vector<int> st[maxn];//重鏈上的點(diǎn)存到鏈頂
void dfs1(int u){
	sz[u]=1;
	for(int v:E[u]){
		if(v==father[u]) continue;
		father[v]=u;
		father_pos[v]=++tot;
		cluster[tot].u=u,cluster[tot].v=v,cluster[tot].id=tot,cluster[tot].k=1,cluster[tot].b=0;
		dfs1(v);
		if(sz[v]>sz[son[u]]) son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
	st[tp].push_back(u);
	if(son[u]!=0) dfs2(son[u],tp);
	for(int v:E[u]){
		if(v==father[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
vector<int> vec[maxn];
vector<int> pre[maxn];
int solve(int l,int r,int u){
    if(l>r) return 0;
	if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=solve(l,mid,u);
	int rson=solve(mid+1,r,u);
	int res=++tot;
	cluster[tot].id=tot;
	rake(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
int calc(int l,int r,int u){
    if(l>r) return 0;
    if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=calc(l,mid,u);
	int rson=calc(mid+1,r,u);
	int res=++tot;
    cluster[tot].id=tot;
	compress(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
void dfs3(int u){
	for(int x:st[u]){
        if(son[x]==0) continue;
		pre[x].push_back(0);
		vec[x].push_back(0);
		for(int v:E[x]){
			if(v!=son[x]&&v!=father[x]){
				dfs3(v);
				//收縮 (x,v) 一個(gè)簇
				vec[x].push_back(v);
			}
		}
		//在對這些輕兒子簇按中點(diǎn)分治的方法合并起來
		for(int i=1;i<=vec[x].size()-1;i++){
			pre[x].push_back(pre[x][i-1]+sz[vec[x][i]]);
		}
		int rt=solve(1,vec[x].size()-1,x);
		if(rt!=0){
		    tot++;
		    cluster[tot].id=tot;
            rake(cluster[rt],cluster[father_pos[son[x]]],cluster[tot]);
            father_pos[son[x]]=tot;//rake 到重鏈上
		}
	}
	vec[u].clear();
	pre[u].clear();
	pre[u].push_back(0);
	vec[u].push_back(0);
	for(int x:st[u]){
		vec[u].push_back(x);
	}
	for(int i=1;i<=vec[u].size()-1;i++){
		pre[u].push_back(pre[u][i-1]+sz[father[vec[u][i]]]-sz[vec[u][i]]);
	}
	if(u!=1) father_pos[u]=calc(1,vec[u].size()-1,u);//把重鏈上的邊 compress 成一條
	else father_pos[u]=calc(2,vec[u].size()-1,u);
	E[u].clear();
	E[u].push_back(father[u]);
	return ;
}
int sum;
int main(){
    read(n);
    read(m);
    for(int i=2;i<=n;i++){
        int p;
        read(p);
        E[p].push_back(i);
        E[i].push_back(p);
    }
    for(int i=1;i<=n;i++) read(a[i]);
    dfs1(1);
    dfs2(1,1);
    dfs3(1);
    while(m--){
        int x,v;
        read(x);
        read(v);
        a[x]=v;
        update(pos[x]);
        write(((1ll*cluster[root].k*a[cluster[root].v]+cluster[root].b)+a[cluster[root].u])%mod);
        putchar('\n');
    }
	return 0;
}

分治計(jì)算貢獻(xiàn)

洛谷 P3781 切樹游戲

注意到 Top tree 本身可以是一種樹分治。

按照 Top tree 維護(hù)點(diǎn)集的套路，我們不將上下界點(diǎn)的異或值計(jì)入狀態(tài)貢獻(xiàn)，但是還是要開 dp 數(shù)組記錄上下界點(diǎn)選或不選的 dp 值。

定義 \(F_i,G_i,D_i,Z_i\) 分別表示簇內(nèi)選出一些點(diǎn)（不能選一個(gè)界點(diǎn)，可以選一個(gè)其他節(jié)點(diǎn)或者兩個(gè)界點(diǎn)）且只包含上界點(diǎn)，只包含下界點(diǎn)，同時(shí)包含上下界點(diǎn)，上下界點(diǎn)均不包含的答案。有如下轉(zhuǎn)移式（我們均認(rèn)為將簇 \(x,y\) 合并為簇 \(w\)）：

對于一個(gè) compress 節(jié)點(diǎn)：

\(F_{w,i} = \sum_{j \oplus k = i \oplus a_{v}} D_{x,j} \times F_{y,k} + F_{x,i} + D_{x,{i \oplus a_v}}\)

\(G_{w,i} = \sum_{j \oplus k = i \oplus a_v} G_{x,j} \times D_{y,k} + G_{y,i} + D_{y,{i \oplus a_v}}\)

\(D_{w,i} = \sum_{j \oplus k = i \oplus a_v} D_{x,j} \times D_{y,k}\)

\(Z_{w,i} = \sum_{j \oplus k = i \oplus a_v} G_{x,j} \times F_{y,k} + G_{x,i \oplus a_v} + F_{y,i \oplus a_v} + \left[i = a_v \right]\)

對于一個(gè) rake 節(jié)點(diǎn)：

\(F_{w,i} = \sum_{j \oplus k = i} F_{x,j} \times F_{y,k} + \sum_{j \oplus k = i \oplus a_v} D_{x,j} \times F_{y,k} + F_{x,i} + F_{y,i} + D_{x,i \oplus a_v}\)

\(G_{w,i} = G_{y,i}\)

\(D_{w,i} = \sum_{j \oplus k = i} F_{x,j} \times D_{y,k} + \sum_{j \oplus k = i \oplus a_v} D_{x,j} \times D_{y,k} + D_{y,i}\)

\(Z_{u,i} = Z_{x,i} + G_{x,i \oplus a_v} + Z_{y,i}\)

然后你發(fā)現(xiàn)轉(zhuǎn)移的瓶頸是異或卷積以及異或平移下標(biāo)，第一個(gè)可以將原 dp 數(shù)組轉(zhuǎn)變?yōu)?fwt 處理后的形式，第二個(gè)則可以這么解決：

\(a_{i \oplus C} = \sum_{j \oplus k = i} a_i \times \left[k = C \right] = a \otimes \left[i = C \right]\)

從而轉(zhuǎn)變?yōu)楫惢蚓矸e形式用 fwt 處理后的數(shù)組解決。

#include<bits/stdc++.h>
#define int long long
const int mod = 10007;
using namespace std;
const int maxn = 6e4+114;
const int maxv = 128;
struct node{
	int u,v,id;
    int f[maxv],g[maxv],d[maxv],z[maxv];
	char type;
}cluster[maxn];
int tran[maxv][maxv];
int n,m;
int a[maxn];
int pos[maxn],fa[maxn],ls[maxn],rs[maxn];
int root=1;
void compress(node x,node y,node &w){
	w.u=x.u;
	w.v=y.v;
    for(int i=0;i<maxv;i++){
        w.f[i]=((x.d[i]*y.f[i]*tran[a[x.v]][i] + x.f[i] + x.d[i]*tran[a[x.v]][i])%mod);
        w.g[i]=((x.g[i]*y.d[i]*tran[a[x.v]][i] + y.g[i] + y.d[i]*tran[a[x.v]][i]%mod)%mod);
        w.d[i]=((x.d[i]*y.d[i]*tran[a[x.v]][i])%mod);
        w.z[i]=((x.g[i]*y.f[i]*tran[a[x.v]][i] + x.g[i]*tran[a[x.v]][i] + y.f[i]*tran[a[x.v]][i] + tran[a[x.v]][i]+x.z[i]+y.z[i])%mod);
    }
	pos[x.v]=w.id;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='C';
	root=w.id;
}
void rake(node x,node y,node &w){
	//把 x rake 到 y 上
	w.u=x.u;
	w.v=y.v;
	for(int i=0;i<maxv;i++){
        w.f[i]=((x.f[i]*y.f[i] + x.d[i]*y.f[i]*tran[a[x.v]][i] + x.f[i] + y.f[i] + x.d[i]*tran[a[x.v]][i])%mod);
        w.g[i]=((y.g[i])%mod);
        w.d[i]=((x.f[i]*y.d[i] + x.d[i]*y.d[i]*tran[a[x.v]][i] + y.d[i])%mod);
        w.z[i]=((x.z[i] + x.g[i]*tran[a[x.v]][i] + y.z[i] + tran[a[x.v]][i])%mod);
	}
	pos[x.v]=w.id;
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='R';
	root=w.id;
}
void update(int u){
    if(u==0) return ;
    if(cluster[u].type=='C'){
        compress(cluster[ls[u]],cluster[rs[u]],cluster[u]);
        update(fa[u]);
    }else{
        rake(cluster[ls[u]],cluster[rs[u]],cluster[u]);
        update(fa[u]);
    }
}
vector<int> E[maxn];
int father_pos[maxn];
int father[maxn];
int son[maxn],sz[maxn],tot;
vector<int> st[maxn];
int F[maxv],G[maxv],D[maxv],Z[maxv];
void dfs1(int u){
	sz[u]=1;
	for(int v:E[u]){
		if(v==father[u]) continue;
		father[v]=u;
		father_pos[v]=++tot;
		cluster[tot].u=u,cluster[tot].v=v,cluster[tot].id=tot;
		for(int i=0;i<maxv;i++) cluster[tot].f[i]=F[i],cluster[tot].g[i]=(G[i]),cluster[tot].d[i]=(D[i]),cluster[tot].z[i]=(Z[i]);
		dfs1(v);
		if(sz[v]>sz[son[u]]) son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
	st[tp].push_back(u);
	if(son[u]!=0) dfs2(son[u],tp);
	for(int v:E[u]){
		if(v==father[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
vector<int> vec[maxn];
vector<int> pre[maxn];
int solve(int l,int r,int u,char type){
    if(l>r) return 0;
	if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=solve(l,mid,u,type);
	int rson=solve(mid+1,r,u,type);
	int res=++tot;
	cluster[tot].id=tot;
	if(type=='R') rake(cluster[lson],cluster[rson],cluster[res]);
	else compress(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
void dfs3(int u){
	for(int x:st[u]){
        if(son[x]==0) continue;
		pre[x].push_back(0);
		vec[x].push_back(0);
		for(int v:E[x]){
			if(v!=son[x]&&v!=father[x]){
				dfs3(v);
				vec[x].push_back(v);
			}
		}
		for(int i=1;i<=vec[x].size()-1;i++){
			pre[x].push_back(pre[x][i-1]+sz[vec[x][i]]);
		}
		int rt=solve(1,vec[x].size()-1,x,'R');
		if(rt!=0){
		    tot++;
		    cluster[tot].id=tot;
            rake(cluster[rt],cluster[father_pos[son[x]]],cluster[tot]);
            father_pos[son[x]]=tot;
		}
	}
	vec[u].clear();
	pre[u].clear();
	pre[u].push_back(0);
	vec[u].push_back(0);
	for(int x:st[u]){
		vec[u].push_back(x);
	}
	for(int i=1;i<=vec[u].size()-1;i++){
		pre[u].push_back(pre[u][i-1]+sz[father[vec[u][i]]]-sz[vec[u][i]]);
	}
	if(u!=1) father_pos[u]=solve(1,vec[u].size()-1,u,'C');
	else father_pos[u]=solve(2,vec[u].size()-1,u,'C');
	E[u].clear();
	E[u].push_back(father[u]);
	return ;
}
void fwt_xor(int *Q,int x=1){
    for(int o=2,k=1;o<=maxv;o<<=1,k<<=1){
        for(int i=0;i<maxv;i+=o)
            for(int j=0;j<k;j++) Q[i+j]=(Q[i+j]+Q[i+j+k])%mod,Q[i+j+k]=(Q[i+j]+mod+mod-Q[i+j+k]-Q[i+j+k])%mod,Q[i+j]=Q[i+j]*x%mod,Q[i+j+k]=Q[i+j+k]*x%mod;
    }
}
int mx;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    D[0]=1;
    fwt_xor(F);
    fwt_xor(G);
    fwt_xor(D);
    fwt_xor(Z);
    for(int i=0;i<maxv;i++){
        tran[i][i]=1;
        fwt_xor(tran[i]);
    }
    cin>>n>>mx;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        int u,v;
        cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1);
    dfs2(1,1);
    dfs3(1);
    cin>>m;
    while(m--){
        string opt;
        cin>>opt;
        if(opt=="Change"){
            int x,y;
            cin>>x>>y;
            a[x]=y;
            update(pos[x]);
        }else{
            int k;
            cin>>k;
            for(int i=0;i<maxv;i++) F[i]=cluster[root].f[i],G[i]=cluster[root].g[i],D[i]=cluster[root].d[i],Z[i]=cluster[root].z[i];
            fwt_xor(F,(mod+1)/2);
            fwt_xor(G,(mod+1)/2);
            fwt_xor(D,(mod+1)/2);
            fwt_xor(Z,(mod+1)/2);
            cout<<(F[k^a[cluster[root].u]]+G[k^a[cluster[root].v]]+D[k^a[cluster[root].u]^a[cluster[root].v]]+Z[k]+(k==a[cluster[root].u])+(k==a[cluster[root].v]))%mod<<'\n';
        }
    }
    return 0;
}

鄰域上的 dp

能維護(hù)子樹鏈的 dp 的結(jié)構(gòu)不少，看看鄰域上的 dp 的維護(hù)。

P8498 樹上鄰域數(shù)點(diǎn)

找到最大的被給定鄰域覆蓋的簇，它在 Top tree 上的子樹內(nèi)的簇同樣被完全覆蓋，提示我們可以處理出每個(gè)鄰域的信息，而由于它的父親沒有被完全覆蓋，所以 \(d < sz_{fa}\)，并且在這個(gè)簇外的鄰域形如以界點(diǎn)為根的子樹中深度不超過 \(d - dis_{u,v}\) 的所有點(diǎn)的深度信息，而這個(gè)深度顯然小于 \(sz_{fa}\)，并且對于一個(gè)父親簇需要處理的界點(diǎn)只有 \(4\) 個(gè)，而 Top tree 的樹高為 \(\log n\) 代表其子樹大小和為 \(O(n \log n)\) 級別。總之，如果我們有辦法求出這 \(O(n \log n)\) 個(gè)信息，就有可能做到快速合并。

由于狀態(tài)總量很少，考慮 dp。

我們定義 \(dp_{u,0/1,i}\) 表示簇 \(u\) 的上界點(diǎn)與下界點(diǎn)在其簇內(nèi)的 \(i\) 鄰域信息，顯然有 \(i \leq sz_u\)，所以在構(gòu)建 Top tree 時(shí)可以在 rake 與 compress 時(shí)暴力合并，總合并量級還是 \(O(n \log n)\) 的。同時(shí)在這個(gè)過程中順便維護(hù)出每個(gè)簇所有邊集與以其兩個(gè)界點(diǎn)為點(diǎn)集的信息，

然后考慮換根 dp。

定義 \(g_{u,0/1,i}\) 表示簇 \(u\) 的上界點(diǎn)與下界點(diǎn)在簇外的 \(i\) 鄰域信息，我們在知道 \(g_{u,0/1,i}\) 與 \(f_{ls_{u},0/1.i}\) 后可以 \(O(sz_{u})\) 地求出 \(g_{u,0/1,i}\) 這個(gè)狀態(tài)數(shù)位 \(O(sz_u)\) 個(gè)的 dp 數(shù)組。那么便從上到下的 dp 求解出所有 \(g_{u,0/1,i}\)。

#ifndef CIRCLE_H
#define CIRCLE_H
#include<vector>
struct info{
  unsigned val;
  unsigned poi[2];
};
const info emptyinfo=info{0,(unsigned)-1,(unsigned)-1};
info MR(info a,info b);
info MC(info a,info b);
void init(int T,int n,int q,std::vector<int>dad,std::vector<info>ve,int M);
bool isempty(info a);
info ask(int x,int d);
#endif
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+114;
vector<int> E[maxn];
info edge[maxn];//點(diǎn) i 到其父親的信息
struct node{
	int u,v,id,dis;//包括界點(diǎn)
	int len,maxu,maxv;//維護(hù)直徑
	vector<info> fu,fv,gu,gv;//子樹內(nèi)距離兩個(gè)界點(diǎn) k 鄰域信息/子樹外距離兩個(gè)界點(diǎn) k 鄰域信息 第一個(gè)處理到自己簇大小 第二個(gè)處理到父親簇大小
	info all;//整個(gè)簇的信息
 	char type;
	//u 在上面 v 在下面
}cluster[maxn];
int pos[maxn],fa[maxn],ls[maxn],rs[maxn];//pos 表示每個(gè)點(diǎn)所在的最小簇
char type[maxn];//P 是邊點(diǎn) C 是 compress 點(diǎn) R 是 rake 點(diǎn)
int root=1;//根簇
info R(info a,info b){
    if(isempty(a)==true) return b;
    if(isempty(b)==true) return a;
    return MR(a,b);
}
info C(info a,info b){
    if(isempty(a)==true) return b;
    if(isempty(b)==true) return a;
    return MC(a,b);
}
info queryf(node &u,int p,char type){
    if(p>=(int)u.fu.size()) p=(int)u.fu.size()-1;
    if(p<0) return emptyinfo;
    else return (type=='u'?u.fu[p]:u.fv[p]);
}
info queryg(node &u,int p,char type){
    if(p>=(int)u.gu.size()) p=(int)u.gu.size()-1;
    if(p<0) return emptyinfo;
    else return (type=='u'?u.gu[p]:u.gv[p]);
}
void compress(node &x,node &y,node &w){
	//x 在上面 y 在下面
	w.u=x.u,w.v=y.v;
    w.len=max(max(x.len,y.len),x.maxv+y.maxu);
    w.maxu=max(x.maxu,x.dis+y.maxu);
    w.maxv=max(y.maxv,y.dis+x.maxv);
    w.dis=x.dis+y.dis;
    w.all=C(x.all,y.all);
    w.fu.push_back(emptyinfo);
    w.fv.push_back(emptyinfo);
    for(int i=1;i<=w.len;i++){
        w.fu.push_back(C(queryf(x,i,'u'),queryf(y,i-x.dis,'u')));
        w.fv.push_back(C(queryf(x,i-y.dis,'v'),queryf(y,i,'v')));
    }
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='C';
	root=w.id;
}
void rake(node &x,node &y,node &w){
	//把 x rake 到 y 上
	w.u=y.u,w.v=y.v;
	w.len=max(max(x.len,y.len),y.maxu+x.maxu);
    w.maxu=max(x.maxu,y.maxu);
    w.maxv=max(y.maxv,x.maxu+y.dis);
	w.dis=y.dis;
	w.all=R(y.all,x.all);
	w.fu.push_back(emptyinfo);
	w.fv.push_back(emptyinfo);
	for(int i=1;i<=w.len;i++){
        w.fu.push_back(R(queryf(y,i,'u'),queryf(x,i,'u')));
        w.fv.push_back(R(queryf(y,i,'v'),queryf(x,i-y.dis,'u')));
    }
	fa[x.id]=fa[y.id]=w.id;
	ls[w.id]=x.id;
	rs[w.id]=y.id;
	w.type='R';
	root=w.id;
}
int father_pos[maxn];//一個(gè)點(diǎn)到其父親的邊的簇編號
int father[maxn];
int son[maxn],sz[maxn],tot,dep[maxn];
int top[maxn];
vector<int> st[maxn];//重鏈上的點(diǎn)存到鏈頂
void dfs1(int u){
	sz[u]=1;
	for(int v:E[u]){
        dep[v]=dep[u]+1;
        father[v]=u;
		father_pos[v]=++tot;
		pos[u]=pos[v]=tot;
		cluster[tot].u=u,cluster[tot].v=v,cluster[tot].id=tot,cluster[tot].dis=1,cluster[tot].len=1,cluster[tot].maxu=1,cluster[tot].maxv=1,cluster[tot].all=edge[v],cluster[tot].fu.push_back(emptyinfo),cluster[tot].fu.push_back(edge[v]),cluster[tot].fv.push_back(emptyinfo),cluster[tot].fv.push_back(edge[v]);
		dfs1(v);
		if(sz[v]>sz[son[u]]) son[u]=v;
		sz[u]+=sz[v];
	}
}
void dfs2(int u,int tp){
    top[u]=tp;
	st[tp].push_back(u);
	if(son[u]!=0) dfs2(son[u],tp);
	for(int v:E[u]){
		if(v==son[u]) continue;
		dfs2(v,v);
	}
}
int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=father[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}
int dis(int u,int v){
    return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
vector<int> vec[maxn];
vector<int> pre[maxn];
int solve(int l,int r,int u){
	if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=solve(l,mid,u);
	int rson=solve(mid+1,r,u);
	int res=++tot;
	cluster[tot].id=tot;
	rake(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
int calc(int l,int r,int u){
    if(l==r) return father_pos[vec[u][l]];
	int L=l,R=r;
	while(L+1<R){
		int mid=(L+R)>>1;
		if((pre[u][mid]-pre[u][l-1])*2<=(pre[u][r]-pre[u][l-1])) L=mid;
		else R=mid;
	}
	int mid=L;
	int lson=calc(l,mid,u);
	int rson=calc(mid+1,r,u);
	int res=++tot;
    cluster[tot].id=tot;
	compress(cluster[lson],cluster[rson],cluster[res]);
	return res;
}
void dfs3(int u){
	for(int x:st[u]){
        if(son[x]==0) continue;
		pre[x].push_back(0);
		vec[x].push_back(0);
		for(int v:E[x]){
			if(v!=son[x]){
				dfs3(v);
				//收縮 (x,v) 一個(gè)簇
				vec[x].push_back(v);
			}
		}
		//在對這些輕兒子簇按中點(diǎn)分治的方法合并起來
		for(int i=1;i<=(int)vec[x].size()-1;i++){
			pre[x].push_back(pre[x][i-1]+sz[vec[x][i]]);
		}
		if(vec[x].size()>=2){
            int rt=solve(1,(int)vec[x].size()-1,x);
            if(rt!=0){
                tot++;
                cluster[tot].id=tot;
                rake(cluster[rt],cluster[father_pos[son[x]]],cluster[tot]);
                father_pos[son[x]]=tot;//rake 到重鏈上
            }
		}
	}
	vec[u].clear();
	pre[u].clear();
	pre[u].push_back(0);
	vec[u].push_back(0);
	for(int x:st[u]){
		vec[u].push_back(x);
	}
	for(int i=1;i<=(int)vec[u].size()-1;i++){
		pre[u].push_back(pre[u][i-1]+sz[father[vec[u][i]]]-sz[vec[u][i]]);
	}
	if(u!=1) father_pos[u]=calc(1,(int)vec[u].size()-1,u);//把重鏈上的邊 compress 成一條
	else father_pos[u]=calc(2,(int)vec[u].size()-1,u);
	E[u].clear();
	E[u].push_back(father[u]);
	return ;
}
void DP(int u){
    if(ls[u]==0) return ;
    if(cluster[u].type=='C'){
        cluster[ls[u]].gu.push_back(emptyinfo);
        cluster[ls[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[ls[u]].gu.push_back(queryg(cluster[u],i,'u')),cluster[ls[u]].gv.push_back(C(queryf(cluster[rs[u]],i,'u'),queryg(cluster[u],i-cluster[rs[u]].dis,'v')));
        cluster[rs[u]].gu.push_back(emptyinfo);
        cluster[rs[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[rs[u]].gu.push_back(C(queryf(cluster[ls[u]],i,'v'),queryg(cluster[u],i-cluster[ls[u]].dis,'u'))),cluster[rs[u]].gv.push_back(queryg(cluster[u],i,'v'));
    }else{
        cluster[ls[u]].gu.push_back(emptyinfo);
        cluster[ls[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[ls[u]].gu.push_back(R(queryg(cluster[u],i,'u'),C(queryf(cluster[rs[u]],i,'u'),queryg(cluster[u],i-cluster[rs[u]].dis,'v')))),cluster[ls[u]].gv.push_back(emptyinfo);
        cluster[rs[u]].gu.push_back(emptyinfo);
        cluster[rs[u]].gv.push_back(emptyinfo);
        for(int i=1;i<=cluster[u].len;i++) cluster[rs[u]].gu.push_back(R(queryg(cluster[u],i,'u'),queryf(cluster[ls[u]],i,'u'))),cluster[rs[u]].gv.push_back(queryg(cluster[u],i,'v'));
    }
    DP(ls[u]);
    DP(rs[u]);
    //默認(rèn)將界點(diǎn) u 的簇外信息合并上自己簇的信息
    for(int i=0;i<=cluster[u].len;i++){
        cluster[ls[u]].gu[i]=C(cluster[ls[u]].gu[i],cluster[ls[u]].all);
        cluster[rs[u]].gu[i]=C(cluster[rs[u]].gu[i],cluster[rs[u]].all);
    }
}//Top tree 上換根 dp
char check(node &u,int p){
    if(p==u.u) return 'u';
    else return 'v';
}
info ask(int u, int d){
    if(d==0) return emptyinfo;
    int now=pos[u];
    while(cluster[fa[now]].len<d) now=fa[now];
    return C(queryg(cluster[now],d-dis(cluster[now].u,u),'u'),queryg(cluster[now],d-dis(cluster[now].v,u),'v'));
}
void init(int T, int n, int q, vector<int> FA, vector<info> e, int M){
    for(int i=1;i<n;i++){
        E[FA[i-1]].push_back(i+1);
        edge[i+1]=e[i-1];
    }
    dfs1(1);
    dfs2(1,1);
    dfs3(1);
    DP(root);
    cluster[root].len=n;
    return ;
}

其他應(yīng)用

待補(bǔ)充。

posted @ 2024-07-05 15:10 ChiFAN鴨閱讀(869) 評論(0) 收藏舉報(bào)

刷新頁面返回頂部

chifan-duck