[ZJOI2008]树的统计Count
Time Limit:10000MS Memory Limit:165536K
Total Submit:116 Accepted:61
Case Time Limit:1000MS
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
Source
额。。我的算法极慢，卡着时间过了。。
一般的算法就是Link—Cut树，树链剖分啊什么的，由于我太菜，只好想了个很SB的算法，我想的是可以不可以用类似于块状数组的办法来解决这道题目。。那么把这个树分成Sqrt（N）左右的小块，然后每次往上跳。。可以在Sqrt（N）中解决问题。。关键是怎么划分。。我TLE了N次主要就是在尝试划分的办法囧。。搞了半天最后稀里糊涂弄出来了。。我真是菜死了囧。。。
改进了一下Code。。变快一点了。。
Code：
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int inf=~0U>>1,maxn=30000;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],Lim,dep[maxn],Fa[maxn];
int own[maxn],Max[maxn],Sum[maxn]={};
void Build(int t,int f,int d)
{
dep[t]=d;Fa[t]=f;
if(own[t]==-1)
{
own[t]=t;
Sum[t]++;
}
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(Sum[tmp]<Lim)
{
Et[t].pb(*e);
own[*e]=tmp;
Sum[tmp]++;
}
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
Sum[t]=s+=w[t];Max[t]=m=max(m,w[t]);
tr(e,Et[t])Dfs(*e,s,m);
}
void Change(int t,int u)
{
w[t]=u;
if(t==own[t])Dfs(t,0,-inf);
else Dfs(t,Sum[Fa[t]],Max[Fa[t]]);
}
int QSum(int a,int b)
{
int s=0;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b]||own[a]==a)
s+=w[a],a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
s+=Sum[a],a=Fa[own[a]];
}
}
return s+w[a];
}
int QMax(int a,int b)
{
int m=-inf;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b])
m=max(m,w[a]),a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
m=max(m,Max[a]),a=Fa[own[a]];
}
}
return max(m,w[a]);
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);int s,t;Lim=sqrt(n)+1;
rep(i,n-1)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)scanf("%d",w+i);
memset(own,-1,sizeof own);
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else if(cmd[1]==’S’)printf("%dn",QSum(s-1,t-1));
else printf("%dn",QMax(s-1,t-1));
}
}