hdu 6430 TeaTree 线段树合并

偏执的太偏执、 2022-04-25 08:04 210阅读 0赞

题意：一棵树上每个节点权值为v\[i\]，每个节点的heard值是：以它为LCA的两个节点的GCD的最大值，要求输出每个节点的heard值

分析：线段树合并，对每个节点建一棵线段树，第x个位置就表示v\[i\]有值为x的因子，只要2个节点有相同的因子就维护答案，每次都把所有子节点的线段树与父节点合并。写法是建立n个线段树，每个线段树保存的是该点权值的所有因数，线段树区间\[l,r\]表示区间l-r范围内最大的因数，首先将1e5个数的所有因数打表，然后再将n个点的权值建线段树。

代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int maxn=1e5+10;
    int rt[maxn],ls[maxn*400],rs[maxn*400],sum[maxn*400];
    vector<int>G[maxn],fac[maxn];
    int cnt=0,sz=1e5,ans[maxn];
    void init(){
    	for(int i=1;i<maxn;i++)
            for(int j=i;j<maxn;j+=i)
                fac[j].push_back(i);//将每个数的所有因数保存起来
    }
    
    void update(int k,int l,int r,int &o){
    	if(!o)o=++cnt;
    	if(l==r){
    		sum[o]=k;
    		return;
    	}
    	int m=(l+r)/2;
    	if(k<=m)update(k,l,m,ls[o]);
    	else update(k,m+1,r,rs[o]);
    	sum[o]=max(sum[ls[o]],sum[rs[o]]);
    }
    
    int merge(int o,int pre,int& v){
    	if(!o||!pre)return o|pre;//将父线段树的因数和儿子线段树因数合并到父线段树，
    	if(sum[o]==sum[pre])v=max(v,sum[o]);
    	if(ls[o]|ls[pre])ls[o]=merge(ls[o],ls[pre],v);//父线段树和儿子线段树左节点都是空的，就不用遍历合并
    	if(rs[o]|rs[pre])rs[o]=merge(rs[o],rs[pre],v);
    	return o;
    }
    
    void dfs(int u){
    	ans[u]=-1;
    	for(int i=0;i<G[u].size();i++){
    		int v=G[u][i];
    		dfs(v);
    		merge(rt[u],rt[v],ans[u]);
    	}
    }
    
    int main(){
    	int n,v;
    	init();
    	scanf("%d",&n);
    	for(int i=2;i<=n;i++){
    		scanf("%d",&v);
    		G[v].push_back(i);
    	}
    	for(int i=1;i<=n;i++){
    		scanf("%d",&v);
    		for(int j=0;j<fac[v].size();j++)
    		update(fac[v][j],1,sz,rt[i]);
    	}
    	dfs(1);
    	for(int i=1;i<=n;i++)
            printf("%d\n",ans[i]);
        return 0;
    }