1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 21574 Solved: 8759
[Submit][Status][Discuss]

Description

　　一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成
一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身

Input

　　输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有
一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作
的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output

　　对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

树链剖分

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 using namespace std;
  6 
  7 const int maxn=30005;
  8 const int INF=0x7ffffff;
  9 
 10 struct line
 11 {
 12     int to,next;
 13 }E[maxn<<1];
 14 int cnt,head[maxn];
 15 
 16 struct data
 17 {
 18     int l,r,mx,sum;
 19 }tree[maxn<<2];
 20 
 21 int n,q,size;
 22 int v[maxn],d[maxn],s[maxn],f[maxn],p[maxn],bl[maxn];
 23 
 24 void insert(int u,int v)
 25 {
 26     E[++cnt].to=v;E[cnt].next=head[u];head[u]=cnt;
 27     E[++cnt].to=u;E[cnt].next=head[v];head[v]=cnt;
 28 }
 29 
 30 void dfs1(int x)
 31 {
 32     s[x]=1;
 33     for(int i=head[x];i;i=E[i].next)
 34     {
 35         if(E[i].to==f[x]) continue;
 36         d[E[i].to]=d[x]+1;
 37         f[E[i].to]=x;
 38         dfs1(E[i].to);
 39         s[x]+=s[E[i].to];
 40     }
 41 }
 42 
 43 void dfs2(int x,int ch)
 44 {
 45     int k=0;size++;
 46     p[x]=size;
 47     bl[x]=ch;
 48     for(int i=head[x];i;i=E[i].next)
 49         if(d[E[i].to]>d[x]&&s[E[i].to]>s[k])
 50             k=E[i].to;
 51     if(k==0) return;
 52     dfs2(k,ch);
 53     for(int i=head[x];i;i=E[i].next)
 54         if(d[E[i].to]>d[x]&&k!=E[i].to)
 55             dfs2(E[i].to,E[i].to);
 56 }
 57 
 58 void build(int k,int l,int r)
 59 {
 60     tree[k].l=l;tree[k].r=r;
 61     if(l==r) return;
 62     int mid=(l+r)>>1;
 63     build(k<<1,l,mid);
 64     build(k<<1|1,mid+1,r);
 65 }
 66 
 67 void update(int k,int x,int y)
 68 {
 69     int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1;
 70     if(l==r){tree[k].sum=tree[k].mx=y;return;}
 71     if(x<=mid) update(k<<1,x,y);
 72     else update(k<<1|1,x,y);
 73     tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
 74     tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);
 75 }
 76 
 77 int querysum(int k,int s,int t)
 78 {
 79     int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1;
 80     if(s==l&&t==r) return tree[k].sum;
 81     if(t<=mid) return querysum(k<<1,s,t);
 82     if(s>mid) return querysum(k<<1|1,s,t);
 83     return querysum(k<<1,s,mid)+querysum(k<<1|1,mid+1,t);
 84 }
 85 
 86 int querymx(int k,int s,int t)
 87 {
 88     int l=tree[k].l,r=tree[k].r,mid=(l+r)>>1;
 89     if(s==l&&t==r) return tree[k].mx;
 90     if(t<=mid) return querymx(k<<1,s,t);
 91     if(s>mid) return querymx(k<<1|1,s,t);
 92     return max(querymx(k<<1,s,mid),querymx(k<<1|1,mid+1,t));
 93 }
 94 
 95 int solvesum(int x,int y)
 96 {
 97     int sum=0;
 98     while(bl[x]!=bl[y])
 99     {
100         if(d[bl[x]]<d[bl[y]]) swap(x,y);
101         sum+=querysum(1,p[bl[x]],p[x]);
102         x=f[bl[x]];
103     }
104     if(p[x]>p[y]) swap(x,y);
105     sum+=querysum(1,p[x],p[y]);
106     return sum;
107 }
108 
109 int solvemx(int x,int y)
110 {
111     int mx=-INF;
112     while(bl[x]!=bl[y])
113     {
114         if(d[bl[x]]<d[bl[y]]) swap(x,y);
115         mx=max(mx,querymx(1,p[bl[x]],p[x]));
116         x=f[bl[x]];
117     }
118     if(p[x]>p[y]) swap(x,y);
119     mx=max(mx,querymx(1,p[x],p[y]));
120     return mx;
121 }
122 
123 int main()
124 {
125     scanf("%d",&n);
126     for(int i=1;i<n;i++)
127     {
128         int x,y;
129         scanf("%d %d",&x,&y);
130         insert(x,y);
131     }
132     for(int i=1;i<=n;i++) scanf("%d",&v[i]);
133     dfs1(1);dfs2(1,1);
134     build(1,1,n);
135     for(int i=1;i<=n;i++) update(1,p[i],v[i]);
136     scanf("%d",&q);
137     char ch[10];
138     for(int i=1;i<=q;i++)
139     {
140         int x,y;
141         scanf("%s%d%d",ch,&x,&y);
142         if(ch[0]=='C')
143         {
144             v[x]=y;
145             update(1,p[x],y);
146         }
147         if(ch[1]=='M') printf("%d
",solvemx(x,y));
148         if(ch[1]=='S') printf("%d
",solvesum(x,y));
149     }
150     return 0;
151 }