首页 > 其他分享 >静态 top tree 入门

静态 top tree 入门

时间：2024-07-05 15:22:14浏览次数：16  
标签：入门 int father top tree tot cluster maxn oplus

理论

我们需要一个数据结构维护树上的问题，仿照序列上的问题，我们需要一个方法快速的刻画出信息。

比如说线段树就通过分治的方式来通过将一个区间划分成 \(\log n\) 个区间并刻画出这 \(\log n\) 个区间的信息。

然后我们考虑把这个东西放到树上类比。你发现线段树上每个非叶节点都有两个儿子，那么你划分树上信息的方式应当也满足这个性质，也就是说把树划分成联通子图的过程中，应当每次合并两个联通子图，同时线段树只有两个端点（维护的是区间）所以这个联通子图应当只有两个界点（与其他联通子图公用的点，这里认为维护的是边集信息，联通子图间边集不交）。

接下来我们把一个划分出的联通子图称为簇。初始每条边都是一个簇。在合并簇的过程中合并出新的簇也会以一条边的形式出现在树上用于下一次合并。

合并两个簇

分为两种。

compress

我们将一个二度点缩掉，或者说将对于两条相邻的边，若他们的公共点度数为 \(2\) 那么就把这两条边合并。合并出的新簇包含原来两个簇的边集，我们记这样的点是 C 点。

rake

对于一个度数为 \(1\) 的点 \(u\)，其唯一的边为 \((u,v)\) 我们将 \((u,v)\) 这条边代表的簇与点 \(v\) 任意一个其他的边代表的簇合并。

最后不难发现的是只会剩下一条边。而合并的过程建出一棵树就是 Top tree。

静态构建

实际上根据全局平衡二叉树的建法可以给出一个 \(2 \times \log n\) 树高的构建方法。

首先按全局平衡二叉树的方法对原树划分，然后轻儿子先把所有簇收缩后 rake 到虚父亲上，对于一条轻儿子全部 rake 完成的重链再用全局平衡二叉树对重链的划分方式把重链上所有边 compress 成一条然后向上递归。

不过对于有多个轻儿子的点显然是有问题的。所以对于多个轻儿子在按照重量选取带权中点，每次按照中点分治，两个分治区间内的轻儿子 rake 成一条在 rake 到一起，还是重量平衡的，所以树高 \(2 \times \log n\)。

按照这种方法建树，需要 \(2\) 倍空间。

维护点信息

对于每个簇我们维护的信息不包括界点信息，在合并信息的时候再把删除的界点的信息带上，那么你发现修改点只需要在他被删掉的簇时修改在一路爬上去就行了，时间复杂度是 \(O(\log n)\)。

应用

动态 dp

维护矩阵（线性变换）

ABC351G

对于一个联通子图来说，若其中只有一个叶子的值不确定，我们可以把这个联通子图的根的 dp 值写成关于不确定叶子的值的线性变换形式，对于这道题目而言就是 \(y = k \times x + b\) 的一次函数形式。

更进一步地化简，因为 \(dp_{u} = a_{u} + \prod dp_v\)，而 \(a_u\) 是一个很简单的项，所以不妨对于每个联通子图表示出 \(\prod dp_v = k \times dp_{x} + b\) 这里 \(x\) 表示联通子图中尚未确定的那个点的 \(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 是边点 C 是 compress 点 R 是 rake 点
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];//一个点到其父亲的边的簇编号
int father[maxn];
int son[maxn],sz[maxn],tot;
vector<int> st[maxn];//重链上的点存到链顶
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) 一个簇
				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);
		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;
}

分治计算贡献

洛谷 P3781 切树游戏

注意到 Top tree 本身可以是一种树分治。

按照 Top tree 维护点集的套路，我们不将上下界点的异或值计入状态贡献，但是还是要开 dp 数组记录上下界点选或不选的 dp 值。

定义 \(F_i,G_i,D_i,Z_i\) 分别表示簇内选出一些点（不能选一个界点，可以选一个其他节点或者两个界点）且只包含上界点，只包含下界点，同时包含上下界点，上下界点均不包含的答案。有如下转移式（我们均认为将簇 \(x,y\) 合并为簇 \(w\)）：

对于一个 compress 节点：

\(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]\)

对于一个 rake 节点：

\(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}\)

然后你发现转移的瓶颈是异或卷积以及异或平移下标，第一个可以将原 dp 数组转变为 fwt 处理后的形式，第二个则可以这么解决：

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

从而转变为异或卷积形式用 fwt 处理后的数组解决。

#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

能维护子树链的 dp 的结构不少，看看邻域上的 dp 的维护。

P8498 树上邻域数点

找到最大的被给定邻域覆盖的簇，它在 Top tree 上的子树内的簇同样被完全覆盖，提示我们可以处理出每个邻域的信息，而由于它的父亲没有被完全覆盖，所以 \(d < sz_{fa}\)，并且在这个簇外的邻域形如以界点为根的子树中深度不超过 \(d - dis_{u,v}\) 的所有点的深度信息，而这个深度显然小于 \(sz_{fa}\)，并且对于一个父亲簇需要处理的界点只有 \(4\) 个，而 Top tree 的树高为 \(\log n\) 代表其子树大小和为 \(O(n \log n)\) 级别。总之，如果我们有办法求出这 \(O(n \log n)\) 个信息，就有可能做到快速合并。

由于状态总量很少，考虑 dp。

我们定义 \(dp_{u,0/1,i}\) 表示簇 \(u\) 的上界点与下界点在其簇内的 \(i\) 邻域信息，显然有 \(i \leq sz_u\)，所以在构建 Top tree 时可以在 rake 与 compress 时暴力合并，总合并量级还是 \(O(n \log n)\) 的。同时在这个过程中顺便维护出每个簇所有边集与以其两个界点为点集的信息，

然后考虑换根 dp。

定义 \(g_{u,0/1,i}\) 表示簇 \(u\) 的上界点与下界点在簇外的 \(i\) 邻域信息，我们在知道 \(g_{u,0/1,i}\) 与 \(f_{ls_{u},0/1.i}\) 后可以 \(O(sz_{u})\) 地求出 \(g_{u,0/1,i}\) 这个状态数位 \(O(sz_u)\) 个的 dp 数组。那么便从上到下的 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];//点 i 到其父亲的信息
struct node{
	int u,v,id,dis;//包括界点
	int len,maxu,maxv;//维护直径
	vector<info> fu,fv,gu,gv;//子树内距离两个界点 k 邻域信息/子树外距离两个界点 k 邻域信息 第一个处理到自己簇大小 第二个处理到父亲簇大小
	info all;//整个簇的信息
 	char type;
	//u 在上面 v 在下面
}cluster[maxn];
int pos[maxn],fa[maxn],ls[maxn],rs[maxn];//pos 表示每个点所在的最小簇
char type[maxn];//P 是边点 C 是 compress 点 R 是 rake 点
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];//一个点到其父亲的边的簇编号
int father[maxn];
int son[maxn],sz[maxn],tot,dep[maxn];
int top[maxn];
vector<int> st[maxn];//重链上的点存到链顶
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) 一个簇
				vec[x].push_back(v);
			}
		}
		//在对这些轻儿子簇按中点分治的方法合并起来
		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]);
    //默认将界点 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 ;
}

其他应用

待补充。

标签：入门,int,father,top,tree,tot,cluster,maxn,oplus
From： https://www.cnblogs.com/chifan-duck/p/18285901

相关文章

  • 《python机器学习从入门到高级》
    《python机器学习从入门到高级》分类算法：引言我们在之前的文章已经介绍了机器学习的一些基础概念，当拿到一个数据之后如何处理、如何评估一个模型、以及如何对模型调参等。接下来，我们正式开始学习如何实现机器学习的一些算法。回归和分类是机器学习的两大最基本的问题，对于......
  • 全网最全网络安全入门指南（2024版）零基础可学_网络安全学习指南
    下一个十年的饭碗就是它了！据悉，2019年9月27日，工信部发布**《关于促进网络安全产业发展的指导意见（征求意见稿）》，明确提出2025年培育形成一批营收20亿元以上的网络安全企业，网络安全产业规模超过2000亿元的发展目标；据市场调研机构Gartner预测，我国网络安全预计将以......
  • 三菱FX PLC入门之定时器和计数器
    PLC中，定时器和计数器是两个非常主要的编程元件，是PLC程序编制不可或缺的环节。我在之前的文章中简单地扯了一下这两个元件，而现在就是揭秘时刻了，让我们一起来看看它们的庐山真面目吧！一、定时器说到定时器，其实我们生活中就有很多它的应用，例如洗衣机的定时选择，烤箱的定时旋......
  • threejs入门2：Creating a scene
    参考：https://threejs.org/docs/index.html#manual/en/introduction/Creating-a-sceneThegoalofthissectionistogiveabriefintroductiontothree.js.Wewillstartbysettingupascene,withaspinningcube.Aworkingexampleisprovidedatthebottomof......
  • django学习入门系列之第四点《案例 博客案例》
    文章目录container面板案例博客案例往期回顾container堆叠到两边<divclass="container-fluidclearfix"><divclass="col-sm-9">1</div><divclass="col-sm-3">2</div></div>放在中间<divclass="c......
  • 关于那些想要转行AI的人：送你一份人工智能入门指南以及学习路线资料
    **人工智能是什么？人工智能为何重要？我们应该畏惧人工智能吗？**为什么突然之间所有人都在谈论人工智能？你可能会从网上知道人工智能如何为亚马逊和Google的虚拟助理提供支持，或者人工智能如何一步步地取代所有的工作（有争议的），但是这些文章极少很好的解释人工智能是什么（或者机器人......
  • qt 入门常用类理解(涉及QMessageBox,Layout,Spacers,Splitter,Buuddy,LoginApp,QFile,
    1.QMessageBoxQMessageBox::Yes QApplication::quit();QMessageBox::exec用于在模态（阻塞式）对话框中显示一个消息框，并等待用户的响应。这个函数通常用于在应用程序中显示消息、警告或询问对话框，并等待用户采取适当的操作后继续执行。int QMessageBox::exec()exec 函数没有......
  • 网络安全工程师入门教程（非常详细）从零基础入门到精通，看完这一篇就够了
    前言想要成为网络安全工程师，却苦于没有方向，不知道从何学起的话，下面这篇网络安全入门教程可以帮你实现自己的网络安全工程师梦想，如果想学，可以继续看下去，文章有点长，希望你可以耐心看到最后！1、Web安全相关概念（2周）·熟悉基本概念(SQL注入、上传、XSS、、CSRF、一句话木马......
  • 软件测试入门---（二）
    1.软件生命周期是软件开始研制到最终被废弃不用所经历的各个阶段。瀑布型模型：自上而下有顺序性缺点：测试介入比较晚，回溯成本比较高，测试周期比较长（企业基本不用这个模型）V模型：开发和测试同时进行敏捷开发模型：以人为核心，弱化文档，通过人与人之间的沟通实现需求分析特点：快......
  • 搭建高效攻防靶场vulfocus与Docker仓库管理实战：从听说到入门系列
    搭建高效攻防靶场vulfocus与Docker仓库管理实战：从听说到入门系列vulfocus简介vulfocus，作为一款前沿的漏洞集成平台，它巧妙地将多种最新的CVE漏洞环境封装于Docker容器之中，便于部署与操作，成为提升安全实战技能的理想靶场。用户既可选择在本地VMware环境中亲手搭建，享受从零到一的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99