重鎖断分学習ノート

文書ディレクトリ

板子題

アルゴリズム解析

定義

を実現

前処理

修正

複雑度

コード

板の問題.
テーマ転送ドアというテーマは、ツリー上でポイントのチェーン上または1本のツリーのポイントの重み値を修正し、クエリーすることを要求します.
アルゴリズム解析
LCAを使用することを考慮しますが、倍増の解法は使用できません(倍増はクエリーでのみ修正できません)、新しいアルゴリズムである軽重鎖分割を使用します.まずLCAを学んでこの文章を見てみることをお勧めします.
定義＃テイギ＃
必要な定義をいくつか示します.

息子:サブノードが最も多い息子.

軽息子:ノードの息子が重息子を除く息子.

重辺:重息子の辺です.

軽辺:重辺以外の辺.

重鎖:重辺からなる鎖で、軽息子を起点とする.

インプリメンテーション
プリプロセッシング
予備処置理由は2回dfs組成であった.最初のdfsは,f a,s o n,s i z,d fa,son,siz,d fa,son,siz,dがそれぞれノードの父親,重子,サブツリーノード数,深さを表す配列を処理する必要がある.2回目のdfsでは、i d,t o p,a id,top,a id,top,aはそれぞれノードの新しい番号(dfsが達成した順序)を表し、このノードが存在する重鎖の先端、新しい番号のポイント権は、必ず重息子を先に処理し、dfsを使用することに注意してください.原因は後述する.
変更
チェーンのポイント権をどのように修正したりクエリーしたりしますか?2つの点が同じ重鎖にあるまで、より深い点を重鎖に沿って上にジャンプさせることができます.次に、重い息子を先に処理し、dfsを使用する場合、このような重いチェーン上のノードと1本の木のノードの番号が連続している場合、セグメントツリーを使用してこの問題を解決することができます.1本の木の重み値を処理するときは、i d i id_i idiからi d i+s i z i−1]id_i+siz_i−1.idi+sizi−1.この区間を修正または照会すればよい.
修正した点のi d idは連続しているので,セグメントツリー大法を用いて解決できる.
複雑さ
1つのチェーンを処理する複雑さはΘ ( log ⁡ 2 n )\Theta\left(\log^2n\right) Θ(log 2 n),処理サブツリーの複雑さはΘ ( log ⁡ n )\Theta\left(\log n\right) Θ(logn) .
コード#コード#
ここではこの問題を再帰的なセグメントツリーで解決する.

#include
#define maxn 100039
#define emaxn 200039
using namespace std;
typedef long long ll;

int n,T,root;
ll MOD;

int head[maxn],nex[emaxn],to[emaxn],k;
#define add(x,y) nex[++k]=head[x];\
head[x]=k;\
to[k]=y;
int tmp,x,y;
ll z;
//     
int w[maxn],a[maxn];
int siz[maxn],son[maxn],d[maxn],fa[maxn];
//size Linux   
int id[maxn],top[maxn],cnt;
void dfs1(int num,int pre){
     
	siz[num]=1;
	fa[num]=pre;
	d[num]=d[pre]+1;
	int maxx=0;
	for(int i=head[num];i;i=nex[i])
	    if(to[i]!=pre){
     
	    	dfs1(to[i],num);
	    	if(siz[to[i]]>maxx) maxx=siz[to[i]],son[num]=to[i];
	    	siz[num]+=siz[to[i]];
		}
	return;
}
void dfs2(int num,int topf){
     
	top[num]=topf; id[num]=++cnt;
	if(!son[num]) return;
	dfs2(son[num],topf);
	for(int i=head[num];i;i=nex[i])
		if(to[i]!=fa[num] && to[i]!=son[num])
		    dfs2(to[i],to[i]);
	return;
}
//    
//       
int L,R;
ll C;
ll sum[maxn<<2],f[maxn<<2];
void up(int rt){
     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%MOD;return;}
void build(int l,int r,int rt){
     
	if(l==r){
     
		sum[rt]=a[l]%MOD;
		return;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	up(rt);
}
void down(int ln,int rn,int rt){
     
	if(f[rt]){
     
		f[rt<<1]+=f[rt]; f[rt<<1]%=MOD;
		f[rt<<1|1]+=f[rt]; f[rt<<1|1]%=MOD;
		sum[rt<<1]+=f[rt]*ln; sum[rt<<1]%=MOD;
		sum[rt<<1|1]+=f[rt]*rn; sum[rt<<1|1]%=MOD;
		f[rt]=0;
	}
	return;
}
void update(int l,int r,int rt){
     
	if(L<=l&&r<=R){
     
		f[rt]+=C;
		sum[rt]+=C*(r-l+1);
		return;
	}
	int m=(l+r)>>1;
	down(m-l+1,r-m,rt);
	if(m>=L) update(l,m,rt<<1);
	if(m<R) update(m+1,r,rt<<1|1);
	up(rt);
}
ll find(int l,int r,int rt){
     
	if(L<=l&&r<=R)
	    return sum[rt];
	int m=(l+r)>>1;
	ll s=0;
	down(m-l+1,r-m,rt);
	if(m>=L) s=(s+find(l,m,rt<<1))%MOD;
	if(m<R) s=(s+find(m+1,r,rt<<1|1))%MOD;
	return s;
}
//       
void init(){
     
	dfs1(root,0);
	dfs2(root,root);
	for(int i=1;i<=n;i++)
	    a[id[i]]=w[i];
	build(1,n,1);
	return;
}
void swap(int &x,int &y) {
     x^=y;y^=x;x^=y;}//   
void updateR(int u,int v,ll c){
     
    C=c;
	while(top[u]!=top[v]){
     
		if(d[top[u]]<d[top[v]]) swap(u,v);
		L=id[top[u]]; R=id[u]; 
		update(1,n,1);
		u=fa[top[u]];
	}
	if(d[u]<d[v]) swap(u,v);
	L=id[v]; R=id[u];
	update(1,n,1);
	return;
}
ll findR(int u,int v){
     
	ll ans=0;
	while(top[u]!=top[v]){
     
		if(d[top[u]]<d[top[v]]) swap(u,v);
		L=id[top[u]]; R=id[u];
		ans+=find(1,n,1);
		ans%=MOD;
		u=fa[top[u]];
	}
	if(d[u]<d[v]) swap(u,v);
	L=id[v]; R=id[u];
	ans+=find(1,n,1);
	return ans;
}
void updateS(int rt,ll c){
     
	L=id[rt]; R=id[rt]+siz[rt]-1; C=c;
	update(1,n,1);
}
ll findS(int rt){
     
	L=id[rt]; R=id[rt]+siz[rt]-1;
	return find(1,n,1);
}
int main(){
     
	scanf("%d%d%d%lld",&n,&T,&root,&MOD);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<n;i++){
     
    	scanf("%d%d",&x,&y);
    	add(x,y) add(y,x)
	}
	init();
	while(T--){
     
		scanf("%d",&tmp);
		if(tmp==1){
     
			scanf("%d%d%lld",&x,&y,&z);
			updateR(x,y,z);
		}
		else if(tmp==2){
     
			scanf("%d%d",&x,&y);
			printf("%lld
",findR(x,y)%MOD);
		}
		else if(tmp==3){
     
			scanf("%d%lld",&x,&z);
			updateS(x,z);
		}
		else{
     
			scanf("%d",&x);
			printf("%lld
",findS(x)%MOD);
		}
	}
	return 0;
}