1 #include<stdio.h>  2 #define maxn 1000  3 struct node{int sum,l,r,laz;};  4 node seg[6*maxn];  5 int tot,n,op,fr[maxn],to[maxn],nxt[maxn],w[maxn];  6 int deep[maxn],fa[maxn],id[maxn],son[maxn],ori[maxn],top[maxn],end[maxn];  7 void adde(int p,int q){to[++tot]=q;nxt[tot]=fr[p];fr[p]=tot;}  8 void swp(int &p,int &q){p^=q;q^=p;p^=q;}  9 int dfs1(int,int); 10 void dfs2(int,int); 11 void push(int); 12 int build(int); 13 void upd(int,int,int,int); 14 int que(int,int,int); 15 int ask(int,int); 16 int main() 17 { 18     scanf("%d%d",&n,&op); 19     int i,p,q; 20     for(i=1;i<n;i++) 21     {scanf("%d%d",&p,&q);adde(p,q);adde(q,p);} 22     for(i=1;i<=n;i++) scanf("%d",&w[i]); 23     tot = 0; top[1] = 1; id[1] = ++tot; ori[1] = w[1]; 24     dfs1(1,0); dfs2(1,0); 25     for(i=1;i<=n;i++) printf("%d ",id[i]); printf("\n");  26     for(i=1;i<=n;i++) printf("%d ",end[i]); printf("\n"); 27     seg[1].l = 1; seg[1].r = n; 28     build(1); 29     //for(i=1;i<30;i++) printf("i %d l %d r %d sum %d\n",i,seg[i].l,seg[i].r,seg[i].sum); 30     char flag[20]; 31     for(i=1;i<=op;i++) 32     { 33         scanf("%s%d%d",flag,&p,&q); 34         if(flag[0]==‘u‘){upd(1,id[p],end[p],q);} 35         else if(flag[0]==‘c‘){upd(1,id[p],id[p],q);} 36         else {printf("%d\n",ask(p,q));} 37     } 38     return 0; 39 } 40 int dfs1(int now,int f) 41 { 42     deep[now] = deep[f]+1; fa[now] = f; 43     int sum=0,maxs=0,siz,i,t; 44     for(i=fr[now];i;i=nxt[i]) 45     { 46         t = to[i]; 47         if(t==f) continue; 48         siz = dfs1(t,now); 49         if(siz>maxs){son[now]=t;maxs=siz;} 50         sum += siz; 51     } 52     return sum+1; 53 } 54 void dfs2(int now,int f) 55 { 56     int s = son[now]; 57     if(s){id[s]=++tot;ori[tot]=w[s];top[s]=top[now];dfs2(s,now);} 58     int i,t; 59     for(i=fr[now];i;i=nxt[i]) 60     { 61         t = to[i]; 62         if(t==s||t==f) continue; 63         id[t] = ++tot; ori[tot] = w[t]; top[t] = t; 64         dfs2(t,now);     65     } 66     end[now] = tot;     67 } 68 void push(int now) 69 { 70     if(seg[now].laz) 71     { 72         int lz = seg[now].laz; seg[now].laz = 0; 73         seg[now].sum += lz*(seg[now].r-seg[now].l+1); 74         if(seg[now].l!=seg[now].r) 75         {seg[now<<1].laz += lz; seg[(now<<1)|1].laz += lz;}  76     }     77 } 78 int build(int now) 79 { 80     node t = seg[now]; 81     if(t.l==t.r){seg[now].sum=ori[t.l];return seg[now].sum;} 82     int mid = (t.l+t.r)>>1; int lc = now<<1; int rc = lc|1; 83     seg[lc].l = t.l; seg[lc].r = mid; 84     seg[rc].l = mid+1; seg[rc].r = t.r; 85     seg[now].sum  = build(lc)+build(rc); 86     return seg[now].sum; 87 } 88 void upd(int now,int l,int r,int w) 89 { 90     push(now); 91     if(seg[now].l>r||seg[now].r<l) return; 92     if(l<=seg[now].l&&seg[now].r<=r) 93     { 94         seg[now].laz += w; push(now); 95         return; 96     } 97     int lc = now<<1; int rc = lc|1; 98     upd(lc,l,r,w); upd(rc,l,r,w); 99     seg[now].sum = seg[lc].sum + seg[rc].sum;100 }101 int que(int now,int l,int r)102 {103     push(now);104     if(seg[now].l>r||seg[now].r<l) return 0;105     if(l<=seg[now].l&&seg[now].r<=r) return seg[now].sum;106     return que(now<<1,l,r) + que((now<<1)|1,l,r);107 }108 int ask(int p,int q)109 {110     int ret = 0;111     int fa1 = top[p]; int fa2 = top[q];112     while(fa1!=fa2)113     {114         if(deep[fa1]<deep[fa2]){swp(fa1,fa2);swp(p,q);}115         ret += que(1,id[fa1],id[p]);116         p = fa[fa1];fa1 = top[p];117     }118     if(deep[p]<deep[q])    swp(p,q);119     return ret+que(1,id[q],id[p]);120 }