2020夏季牛客多校訓練キャンプ第7回(C)A National Pandemic(木鎖断分)

A National Pandemic
原題はこちらをご覧ください
タイトルの説明:
国は、n n n個のノードn−1 n−1 n−1辺の図として表すことができる.F(x)F(x)F(x)はノードx x xの疫病の深刻さを表す.次の3つの変更/クエリーがあります.

疫病はx x xノードで爆発し,重症度はx x x xであり,各ノードy y,F(y)F(y)F(y)増加w−d i s t(x,y)w−dist(x,y)w−dist(x,y)w−dist(x,y)であり,d i s t(x,y)dist(x,y)dist(x,y)dist(x,y)はノードx x xからノードy y y yへの経路上の数を表す.

は、ノードx x xのF(x)F(x)F(x)をm i n(F(x)、0)min(F(x)、0)min(F(x)、0)min(x)に更新する.

ノードx xのF(x)F(x)F(x)

に問い合わせる.
説明を入力:
複数のテスト例があります.入力された第1行は、試験例の数を表す整数T(1≦T≦5)T(1leq Tleq 5)T(1≦T≦5)を含む.各試験例について、第1行は2つの整数n,m(1≦n,m≦5)を含む.× 1 0 4 ) n,m(1\leq n,m\leq 5\times 10 ^ 4) n,m(1≤n,m≤5×104)は、都市の数およびイベントおよびクエリの数を表す.以下のn−1 n−1 n−1行は、それぞれ2つの整数x,y(1≦x,y≦n)x,y(1leq x,yleq n)x,y(1≦x,y≦n)x,y(1≦x,y≦n)を含み、都市x xとy y y yの間の道路を表す.以下のm m行はすべてのイベントを記述し、各イベントは整数o p t(1≦o p t≦3)mathit{opt}(1leqmathit{opt}leq 3)opt(1≦opt≦3)で開始し、o p tmathit{opt}optが

は同じ行に2つの整数x,w(1≦x≦n,0≦w≦10000)x,w(1leq xleq n,0leq wleq 10000)x,w(1≦x≦n,0≦w≦10000)がある.これは、上述したイベント1を指す.

は、同じ行に整数x(1≦x≦n)x(1leq xleq n)x(1≦x≦n)がある.これはイベント2です.

は、同じ行に整数x(1≦x≦n)x(1leq xleq n)x(1≦x≦n)がある.これは、回答が必要なクエリーです.

出力の説明:
クエリーごとに整数を出力します.
サンプル入力:

1
5 6
1 2
1 3
2 4
2 5
1 1 5
3 4
2 1
1 2 7
3 3
3 1

サンプル出力:

3
9
6

考え方:
まず,各操作を解析した:o p t=1:opt=1:opt=1:木の上で距離を求めるにはl c a lca lcaを用いることができるので,d i s t dist distという関数化を行い,x,y,l c a x,y,lca x,y,lcaの深さをそれぞれd e p[x],d e p[y],d e p[l c a]:dep[x],dep[y],dep[lca]:dep[x],dep[y],dep[lca]: w − d i s t ( x , y ) w-dist(x,y) w−dist(x,y) = w − ( d e p [ x ] + d e p [ y ] − 2 d e p [ l c a ] ) =w-(dep[x]+dep[y]-2dep[lca]) =w−(dep[x]+dep[y]−2dep[lca]) = w − d e p [ x ] − d e p [ y ] + 2 d e p [ l c a ] =w-dep[x]-dep[y]+2dep[lca] =w−dep[x]−dep[y]+2dep[lca]これにより、o p t==1 opt=1 opt=1 opt=1の場合、w−d e p[x]w−dep[x]w−dep[x]w−dep[x]は固定され、各ノードについて、d e p[y]dep[y]dep[y]dep[y]も固定されるので、A+=w−d e p[x]とし、B++A+=w−dep[x]とし、B++A+=w−dep[x]とし、B++A+=w−dep[x]とし、B++A Aはx x x xに関するすべての結果を表す.B B B B Bは、d e p[y]dep[y]dep[y]dep[y]の回数を表すので、操作のたびに、f(y)=A−B∗d e p[y]+2Σ(d e p[l c a])f(y)=A−B*dep[y]+2sum(dep[lca])f(y)=A−B*B*dep[y]=A−B∗dep[y]+2Σ(dep[lca])o p t=2:opt=2:opt=2:opt=2:opt=2:この操作について、考慮する必要がある.正負、したがって、m i n(0,f(y))min(0,f(y))min(0,f(y))を蓄積する必要がある.そこで、yの除去結果を1つの配列で格納します.f f y+=m i n(0,f(y))−f(y)ff_y+=min(0,f(y)−f(y)ffy+=min(0,f(y))−f(y)の後、f f y ff_を加えるだけで答えを算出するy ffyで良い:f(y)=A−B∗d e p[y]+2Σ(d e p[l c a])+f f y f(y)=A−B*dep[y]+2sum(dep[lca])+ff_y f(y)=A−B∗dep[y]+2Σ(dep[lca])+ffy o p t==3 opt=3 opt=3 opt=3出力結果でよい
A C AC AC C o d e Code Code:
コードは私のチームメイトが書いたもので、ブスでブスでブーブー

#include
#include
#include
#define ll long long
#define I1 i<<1
#define I2 i<<1|1
using namespace std;
const int MAXN=1e5+5;
int v[MAXN],h[MAXN],fa[MAXN],id[MAXN],ld[MAXN],rd[MAXN],siz[MAXN],dep[MAXN],son[MAXN],top[MAXN],vis[MAXN],ff[MAXN],n,m,t,x,y,op;
ll cnt,tot,A,B;
struct node{int to,next;}a[MAXN<<1];
struct Tree{int l,r,lz;ll sum;}sgt[MAXN<<2],e[MAXN<<2];
void add(int x,int y){
	a[++cnt].to=y;
	a[cnt].next=h[x];
	h[x]=cnt;
}
void p(int x){
    siz[x]=1;
	son[x]=0;
    for(int i=h[x];~i;i=a[i].next){
        int nxt=a[i].to;
        if(nxt==fa[x])continue;
        fa[nxt]=x;
		dep[nxt]=dep[x]+1;
		p(nxt);
		siz[x]+=siz[nxt];
        if(siz[nxt]>siz[son[x]])
			son[x]=nxt;
    }
}
void dfs(int x,int y){
    top[x]=y;
	ld[x]=++tot;
	id[tot]=x;
    if(son[x]) dfs(son[x],y);
    for(int i=h[x],nxt;~i;i=a[i].next){
        nxt=a[i].to;
        if(nxt^son[x]&&nxt^fa[x])
        	dfs(nxt,nxt);
    }
}
void build(int i,int l,int r){
    sgt[i].l=l;
	sgt[i].r=r;
	sgt[i].lz=0;
    if(l==r){
        sgt[i].sum=v[id[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(I1,l,mid);
    build(I2,mid+1,r);
    sgt[i].sum=sgt[I1].sum+sgt[I2].sum;
}
void down(int x){
    if(sgt[x].lz){
        sgt[x].sum+=sgt[x].lz*(sgt[x].r-sgt[x].l+1);
        sgt[x<<1].lz+=sgt[x].lz;
        sgt[x<<1|1].lz+=sgt[x].lz;
        sgt[x].lz=0;
    }
}
ll q(int x,int l,int r){
    if(sgt[x].l==l&&sgt[x].r==r) return sgt[x].sum+sgt[x].lz*(r-l+1);
    down(x);
	int m=sgt[x].l+sgt[x].r>>1;
    if(r<=m) return q(x<<1,l,r);
    else if(l>m) return q(x<<1|1,l,r);
    else return q(x<<1,l,m)+q(x<<1|1,m+1,r);
}
void ud(int i,int l,int r,ll v){
    if(sgt[i].l==l&&sgt[i].r==r){
		sgt[i].sum+=(r-l+1)*v;
		sgt[i].lz+=v;
		return;
	}
    if(sgt[i].lz) down(i);
    int mid=sgt[i].l+sgt[i].r>>1;
    if(r<=mid)ud(I1,l,r,v);
    else if(l>mid)ud(I2,l,r,v);
    else ud(I1,l,mid,v),ud(I2,mid+1,r,v);
    sgt[i].sum=sgt[I1].sum+sgt[I2].sum;
}
void my(int x,int l,int r,ll val){
    if(sgt[x].l==l&&sgt[x].r==r){
		sgt[x].lz+=val;
		return ;
	}
    sgt[x].sum+=(r-l+1)*val;
    int m=sgt[x].l+sgt[x].r>>1;
    if(r<=m) my(x<<1,l,r,val);
    else if(l>m) my(x<<1|1,l,r,val);
    else my(x<<1,l,m,val),my(x<<1|1,m+1,r,val);
}
void cy(int x,int y,ll val){
    while(top[x]^top[y]){
        if(dep[top[x]]>dep[top[y]]) swap(x,y);
        my(1,ld[top[y]],ld[y],val);
		y=fa[top[y]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    my(1,ld[x],ld[y],val);
}
ll q1(int x,int y){
    ll ret=A-B*dep[x]+ff[x];
    while(top[x]^top[y]){
        if(dep[top[x]]>dep[top[y]]) swap(x,y);
        ret+=q(1,ld[top[y]],ld[y]);
		y=fa[top[y]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return ret+q(1,ld[x],ld[y]);
}
int main(){
    for(scanf("%d",&t);t--;cnt=tot=A=B=0){
        scanf("%d%d",&n,&m);
        memset(h,-1,sizeof(h));
        memset(vis,0,sizeof(vis));
        memset(dep,0,sizeof(dep));
        memset(siz,0,sizeof(siz));
        memset(top,0,sizeof(top));
        memset(rd,0,sizeof(rd));
        memset(ld,0,sizeof(ld));
        memset(ff,0,sizeof(ff));
        for(int i=1;i<n;i++){
        	scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
        dep[1]=1;
		p(1);
		dfs(1,1);
		build(1,1,tot);
        while(m--){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d",&x,&y);
                cy(1,x,2ll),
                A+=y-dep[x];B++;
            }
            else{
                scanf("%d",&x);
                ll val=q1(x,1);
                if(op==2)ff[x]+=min(0ll,val)-val;
                if(op==3)printf("%lld
",val);
            }
        }
    }
}