hdu 5044 Tree

标题:一本の木.2つの点uvパス上のすべての点を重み付けし、パス上のすべてのエッジを重み付けする2つの操作があります.最後に、すべてのポイントの重みとすべてのエッジの重みを出力します.
構想:ツリーチェーン分割+ツリー配列.この問題が出たのは社会に報復するためだと感じて、私は全部で25回ひざまずいた.拡張スタックでも入力フックでもインラインでもあり、最後にはc++で渡すしかなく、g++爆スタックです.しかし、この問題も模範的で、木の鎖の分割の基本的な操作です.エッジの処理を習ったことがないので、エッジをポイントに縛り、クエリーエッジを変更するときに、ルートから離れた方向に接続されたポイントを操作します.また,ツリー配列は区間更新ができないため,更新ごとに始点にkを加算し,終点+1からkを減算する.

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string.h>
#include<cstdio>

using namespace std;

#define maxn 100010
#define ll long long 


int head[maxn];
int next[maxn*2];
int to[maxn*2];
int e2v[maxn]; // i           
int edgeu[maxn];
int edgev[maxn];

int siz[maxn];  // i         
int dep[maxn];  //    
int top[maxn];  //        
int fa[maxn];   //   
int son[maxn];  //   
int w[maxn];    //          
int w_1[maxn];	//       
bool vis[maxn];
int pos;
int end;

int n,m,p;

ll cv[maxn];
ll ce[maxn];
ll ans1[maxn];
ll ans2[maxn];

void scanf_(int &num){
  char in;
  bool neg=false;
  while(((in=getchar()) > '9' || in<'0') && in!='-') ;
  if(in=='-')
  {
    neg=true;
    while((in=getchar()) >'9' || in<'0');
  }
  num=in-'0';
  while(in=getchar(),in>='0'&&in<='9')
    num*=10,num+=in-'0';
  if(neg)
    num=0-num;
}

void init(){
    memset(siz,0,sizeof(siz));
    memset(top,0,sizeof(top));
    memset(son,0,sizeof(son));
    memset(head,-1,sizeof(head));
    memset(cv,0,sizeof(cv));
    memset(ce,0,sizeof(ce));
    pos=0;
    end=0;
}

inline void addedge(int u,int v){
    to[end]=v,next[end]=head[u],head[u]=end++;
    to[end]=u,next[end]=head[v],head[v]=end++;
}

void dfs(int x,int pre){
    vis[x]=1;
    dep[x]=dep[pre]+1;
    fa[x]=pre;
    for(int i=head[x];i!=-1;i=next[i]){
        if(to[i]==pre)continue;
        if(vis[to[i]])continue;
        dfs(to[i],x);
        siz[x]+=siz[to[i]];
        if(son[x]==0)son[x]=to[i];
        else if(siz[son[x]]<siz[to[i]])son[x]=to[i];
    }
    siz[x]++;
}

void dfs2(int x,int pre){
    vis[x]=1;
    pos++;
    w[x]=pos;
    w_1[pos]=x;
    if(son[fa[x]]==x)top[x]=top[fa[x]];
    else top[x]=x;
    //      
    if(son[x]==0)return;
    dfs2(son[x],x);
    for(int i=head[x];i!=-1;i=next[i]){
        if(to[i]==pre)continue;
        if(to[i]==son[x])continue;
        if(vis[to[i]])continue;
        dfs2(to[i],x);
    }
}


inline int lowbit(int x){
	return x&(-x);
}

ll sum(int end,int type){
	if(type==1){
		ll sum=0;
		while(end){
			sum+=cv[end];
			end-=lowbit(end);
		}
		return sum;
	}else{
		ll sum=0;
		while(end){
			sum+=ce[end];
			end-=lowbit(end);
		}
		return sum;
	}
}

void update(int pos,ll num,int type){
	if(type==1){
		while(pos<=n+1){
			cv[pos]+=num;
			pos+=lowbit(pos);
		}
	}else{
		while(pos<=n+1){
			ce[pos]+=num;
			pos+=lowbit(pos);
		}
	}
}

int main(){
    int t;
    cin>>t;
    for(int cas=1;cas<=t;cas++){
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++){
            scanf_(edgeu[i]); scanf_(edgev[i]);
            addedge(edgeu[i],edgev[i]);
        }

        memset(vis,0,sizeof(vis));
        dfs(1,0);
        memset(vis,0,sizeof(vis));
        dfs2(1,0);

        for(int i=1;i<n;i++){
            if(fa[edgeu[i]]==edgev[i]){
                e2v[i]=edgeu[i];
            }else{
                e2v[i]=edgev[i];
            }
        }

        char op[8];
        for(int i=1;i<=m;i++){
            scanf("%s",op);
            int u,v,k;
            scanf_(u); scanf_(v); scanf_(k);
            if(op[3]=='1'){
                while(top[u]!=top[v]){
                    if(dep[top[u]]<dep[top[v]])swap(u,v);
                    update(w[top[u]],k,1);
                    update(w[u]+1,-k,1);
                    u=fa[top[u]];
                }
                if(w[u]>w[v])swap(u,v);
                update(w[u],k,1);
                update(w[v]+1,-k,1);
            }else{
                while(top[u]!=top[v]){
                    if(dep[top[u]]<dep[top[v]])swap(u,v);
                    update(w[top[u]],k,2);
                    update(w[u]+1,-k,2);
                    u=fa[top[u]];
                }
                if(w[u]>w[v])swap(u,v);
                update(w[u]+1,k,2);	//        
                update(w[v]+1,-k,2); 
            }
        }

        printf("Case #%d:
",cas);
        ll t=0;
        for(int i=1;i<=n;i++){
        	t+=sum(i,1);
			t-=sum(i-1,1);
			ans1[i]=t;
        }
        t=0;
        for(int i=1;i<=n;i++){
        	t+=sum(i,2);
			t-=sum(i-1,2);
			ans2[i]=t;
        }
		for(int i=1;i<=n;i++){
            printf("%I64d",ans1[w[i]]);
            if(i!=n)printf(" ");
        }
        printf("
");
        for(int i=1;i<n;i++){
        	printf("%I64d",ans2[w[e2v[i]]]);
            if(i!=n-1)printf(" ");
        }
        printf("
");
    }
    return 0;
}