[ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 14968 Solved: 6079
[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
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
2
2
10
6
5
6
5
16
【分析】很简单的一道树链剖分。唯一要注意的就是负数问题。。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)+1)
using namespace std;
typedef long long ll;
const int N=2e5+;
const int M=N*N+;
int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N],c[N]; //top 最近的重链父节点
int num,n,m;
vector<int> v[N];
struct tree {
int x,y;
void read() {
scanf("%d%d",&x,&y);
}
};
tree e[N];
void dfs1(int u, int f, int d) {
dep[u] = d;
siz[u] = ;
son[u] = ;
fa[u] = f;
for (int i = ; i < v[u].size(); i++) {
int ff = v[u][i];
if (ff == f) continue;
dfs1(ff, u, d + );
siz[u] += siz[ff];
if (siz[son[u]] < siz[ff])
son[u] = ff;
}
}
void dfs2(int u, int tp) {
top[u] = tp;
id[u] = ++num;
if (son[u]) dfs2(son[u], tp);
for (int i = ; i < v[u].size(); i++) {
int ff = v[u][i];
if (ff == fa[u] || ff == son[u]) continue;
dfs2(ff, ff);
}
} struct Tree {
int l,r,val,sum;
};
Tree tree[*N];
void pushup(int x) {
tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);
tree[x].sum=tree[lson(x)].sum+tree[rson(x)].sum;
} void build(int l,int r,int v) {
tree[v].l=l;
tree[v].r=r;
if(l==r) {
tree[v].val = val[l];
tree[v].sum=val[l];
return ;
}
int mid=(l+r)>>;
build(l,mid,v*);
build(mid+,r,v*+);
pushup(v);
}
void update(int o,int v,int val) { //log(n)
if(tree[o].l==tree[o].r) {
tree[o].val =tree[o].sum= val;
return ;
}
int mid = (tree[o].l+tree[o].r)/;
if(v<=mid)
update(o*,v,val);
else
update(o*+,v,val);
pushup(o);
}
int queryMax(int x,int l, int r) {
if (tree[x].l >= l && tree[x].r <= r) {
return tree[x].val;
}
int mid = (tree[x].l + tree[x].r) / ;
int ans = -;
if (l <= mid) ans = max(ans, queryMax(lson(x),l,r));
if (r > mid) ans = max(ans, queryMax(rson(x),l,r));
return ans;
} int Qmax(int u, int v) {
int tp1 = top[u], tp2 = top[v];
int ans = -;
while (tp1 != tp2) {
if (dep[tp1] < dep[tp2]) {
swap(tp1, tp2);
swap(u, v);
}
ans = max(queryMax(,id[tp1], id[u]), ans);
u = fa[tp1];
tp1 = top[u];
}
//if (u == v) return ans;
if (dep[u] > dep[v]) swap(u, v);
ans = max(queryMax(,id[u], id[v]), ans);
return ans;
}
int querySum(int x,int l,int r){
if (tree[x].l >= l && tree[x].r <= r) {
return tree[x].sum;
}
int mid = (tree[x].l + tree[x].r) / ;
int ans = ;
if (l <= mid) ans += querySum(lson(x),l,r);
if (r > mid) ans += querySum(rson(x),l,r);
return ans;
}
int Qsum(int u,int v){
int tp1 = top[u], tp2 = top[v];
int ans = ;
while (tp1 != tp2) {
if (dep[tp1] < dep[tp2]) {
swap(tp1, tp2);
swap(u, v);
}
ans +=querySum(,id[tp1], id[u]);
//printf("ans: %d\n",ans);
u = fa[tp1];
tp1 = top[u];
}
//if (u == v) return ans;
if (dep[u] > dep[v]) swap(u, v);
ans +=querySum(,id[u], id[v]);
return ans;
}
int main() {
scanf("%d",&n);
for(int i=; i<n; i++) {
e[i].read();
v[e[i].x].push_back(e[i].y);
v[e[i].y].push_back(e[i].x);
}
for(int i=;i<=n;i++)scanf("%d",&c[i]);
num = ;
dfs1(,,);
dfs2(,);
for (int i = ; i <=n; i++) {
val[id[i]] = c[i];
}
build(,num,);
char s[];
scanf("%d",&m);
while(m--) {
int x,y;
scanf("%s",&s);
scanf("%d%d",&x,&y);
if(s[]=='M')
printf("%d\n",Qmax(x,y));
else if (s[] == 'H')
update(,id[x],y);
else
printf("%d\n",Qsum(x,y));
}
return ;
}