潇爷昨天刚刚讲完。。。感觉得还可以。。。对着模板打了个模板。。。还是不喜欢用指针。。。。
1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 10559 Solved: 4258
[Submit][Status][Discuss]
Description
一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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
HINT
Source
树的分治
题目标解树的分治，写起来很难。。。而且我也不会。。。。
把树链剖，存储个点的信息。然后hash到线段树上。。。线段树维护区间最大和区间求和即可。。。
模板题，就照着模板来了。。。。我居然也开始压代码了。。（QaQ)
详情分析：http://blog.csdn.net/DaD3zZ/article/details/50628472
代码= =：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 1000000000
struct data1{int l,r,sum,max;}t[120005];
struct data2{int next,go;}edge[60005];
int tree[30005],pre[30005],end[30005],son[30005],fa[30005],data[30005],num[30005],top[30005],deep[30005];
int n,x,y,cnt,tot,Q;
char opt[10];
int max(int a,int b){if (a>b) return a;return b;}
int min(int a,int b){if (a>b) return b;return a;}
void addedge(int u,int v){edge[++cnt].go=v;edge[cnt].next=end[u];end[u]=cnt;}
void dfs_1(int now,int f,int d)
{
deep[now]=d;fa[now]=f;num[now]=1;
for (int i=end[now]; i; i=edge[i].next)
{
int go=edge[i].go;if (go==f) continue;
dfs_1(go,now,d+1);num[now]+=num[go];
if (!son[now] || num[go]>num[son[now]]) son[now]=go;
}
}//链剖dfs_1
void dfs_2(int now,int number)
{
top[now]=number;tree[now]=++tot;
pre[tree[now]]=now;
if (!son[now]) return;
dfs_2(son[now],number);
for (int i=end[now]; i; i=edge[i].next)
{
int go=edge[i].go;
if (go!=son[now] && go!=fa[now]) dfs_2(go,go);
}
}//链剖dfs_2
void updata(int now)
{
t[now].sum=t[now<<1].sum+t[now<<1|1].sum;
t[now].max=max(t[now<<1].max,t[now<<1|1].max);
}//线段树。。
void build(int now,int l,int r)
{
t[now].l=l;t[now].r=r;
if (l==r) {t[now].sum=t[now].max=data[pre[l]];return;}
int mid=(l+r)>>1;
build(now<<1,l,mid);build(now<<1|1,mid+1,r);
updata(now);
}
void insert(int now,int loc,int add)
{
if (t[now].l==t[now].r)
{
t[now].sum+=add*(t[now].r-t[now].l+1);
t[now].max+=add;return;
}
int mid=(t[now].r+t[now].l)>>1;
if (loc<=mid) insert(now<<1,loc,add);else insert(now<<1|1,loc,add);
updata(now);
}
int query_sum(int now,int L,int R)
{
if (L<=t[now].l && R>=t[now].r) return t[now].sum;
int mid=(t[now].r+t[now].l)>>1;int ans=0;
if (L<=mid) ans+=query_sum(now<<1,L,R);
if (mid<R) ans+=query_sum(now<<1|1,L,R);
updata(now);
return ans;
}
int query_max(int now,int L,int R)
{
if (L<=t[now].l && R>=t[now].r) return t[now].max;
int mid=(t[now].l+t[now].r)>>1;int ans=-inf;
if (L<=mid) ans=max(ans,query_max(now<<1,L,R));
if (mid<R) ans=max(ans,query_max(now<<1|1,L,R));
updata(now);
return ans;
}
int find_max(int x,int y)
{
int f1=top[x],f2=top[y],tmp,ans=-inf;
while (f1!=f2)
{
if (deep[f1]<deep[f2]) {tmp=f1;f1=f2;f2=tmp;tmp=x;x=y;y=tmp;}
ans=max(ans,query_max(1,tree[f1],tree[x]));
x=fa[f1];f1=top[x];
}
ans=max(ans,query_max(1,min(tree[x],tree[y]),max(tree[x],tree[y])));
return ans;
}//查询原树上信息的区间最大
int find_sum(int x,int y)
{
int f1=top[x],f2=top[y],tmp,ans=0;
while (f1!=f2)
{
if (deep[f1]<deep[f2]) {tmp=f1;f1=f2;f2=tmp;tmp=x;x=y;y=tmp;}
ans+=query_sum(1,tree[f1],tree[x]);
x=fa[f1];f1=top[x];
}
ans+=query_sum(1,min(tree[x],tree[y]),max(tree[x],tree[y]));
return ans;
}//查询原树上信息的区间和
int main()
{
scanf("%d",&n);
for (int i=1; i<=n-1; i++)
{
scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
for (int i=1; i<=n; i++)
scanf("%d",&data[i]);
dfs_1(1,0,1);dfs_2(1,1);
build(1,1,n);
scanf("%d",&Q);
while (Q)
{
Q--;
scanf("%s%d%d",&opt,&x,&y);
if (opt[0]=='C') insert(1,tree[x],y-data[x]),data[x]=y;
else if (opt[1]=='M') printf("%d
",find_max(x,y));
else if (printf("%d
",find_sum(x,y)));
}
return 0;
}