1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 14982 Solved: 6081
[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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <string.h>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define inf 0x7fffffff
//#define ivorysi
#define mo 97797977
#define hash 974711
#define base 47
#define MAXN 30005
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
//树的存储
struct node {
int to,next;
}edge[MAXN*];
int head[MAXN],sumedge,n,q;
int val[MAXN];//点值 void add(int u,int v) {
edge[++sumedge].to=v;
edge[sumedge].next=head[u];
head[u]=sumedge;
}
//线段树部分变量定义
struct data {
int l,r,//边界
lson,//左儿子（因为不能直接位运算要节省空间）
rson,//右儿子（因为不能直接位运算要节省空间）
sum,//区间总和
maxp,//区间最大值
fa;//单点更新优化
data() {
l=,r=,lson=,rson=,sum=,maxp=-inf,fa=;
}
}tree[MAXN*];
int treecnt;//树点个数
int w[MAXN];//单点更新优化 //剖分部分变量定义
int fa[MAXN],//父亲
dep[MAXN],//深度
size[MAXN],//子树大小
son[MAXN],//重儿子
rank[MAXN],//在链中的位置
belong[MAXN],//属于哪条链
top[MAXN],//这个点所在链的深度最小的点
linkcnt,//链数
lroot[MAXN];//每条链的树根 //剖分部分
void dfs1(int u) {//size,fa,son,dep
size[u]=;
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(v!=fa[u]) {
fa[v]=u;
dep[v]=dep[u]+;
dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
}
void build(int p,int l,int r);
vector<int> line;
void dfs2(int u) {//belong,top,rank
if(!belong[u]) {
belong[u]=++linkcnt;
top[linkcnt]=u;
rank[u]=; }
line.push_back(u);
if(!son[u]) {
lroot[belong[u]]=++treecnt;
build(treecnt,,line.size());
line.clear();
return;
}
belong[son[u]]=belong[u];
rank[son[u]]=rank[u]+;
dfs2(son[u]);
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(v!=son[u] && v!=fa[u])
dfs2(v);
} }
//剖分部分结束
//————————————————————————————
//线段树部分
void build(int p,int l,int r) {
tree[p].l=l;
tree[p].r=r;
if(l==r) {
tree[p].sum=val[line[l-]];
tree[p].maxp=val[line[l-]];
w[line[l-]]=p;
return;
}
int mid=(l+r)>>;
tree[p].lson=++treecnt;
tree[treecnt].fa=p;
build(treecnt,l,mid);
int t1=tree[tree[p].lson].maxp;
int t3=tree[tree[p].lson].sum;
tree[p].rson=++treecnt;
tree[treecnt].fa=p;
build(treecnt,mid+,r);
int t2=tree[tree[p].rson].maxp;
int t4=tree[tree[p].rson].sum;
tree[p].sum+=t3+t4;
tree[p].maxp=max(t1,t2);
return;
}
void change(int u) {
tree[w[u]].sum=tree[w[u]].maxp=val[u];
int z=tree[w[u]].fa;
while(z!=) {
tree[z].sum=tree[tree[z].lson].sum+tree[tree[z].rson].sum;
tree[z].maxp=max(tree[tree[z].lson].maxp,tree[tree[z].rson].maxp);
z=tree[z].fa;
}
}
int treeqsum(int p,int l,int r) {
if(l <= tree[p].l && r >= tree[p].r) {
return tree[p].sum;
}
int mid=(tree[p].l+tree[p].r)>>;
int t1=,t2=;
if(l <= mid) {
t1=treeqsum(tree[p].lson,l,r);
}
if(r > mid){
t2=treeqsum(tree[p].rson,l,r);
}
return t1+t2;
}
int treeqmax(int p,int l,int r) {
if(l <= tree[p].l && r >= tree[p].r) {
return tree[p].maxp;
}
int mid=(tree[p].l+tree[p].r)>>;
int t1=-inf,t2=-inf;
if(l <= mid) {
t1=treeqmax(tree[p].lson,l,r);
}
if(r > mid){
t2=treeqmax(tree[p].rson,l,r);
}
return max(t1,t2);
}
//线段树部分结束
//——————————————————————————
//解决问题部分
int qsum(int u,int v){
int x=top[belong[u]],y=top[belong[v]],res=;
while(belong[u]!=belong[v]) {
if(dep[x]>dep[y]){
res+=treeqsum(lroot[belong[x]],tree[lroot[belong[x]]].l,rank[u]);
u=fa[x];
}
else {
res+=treeqsum(lroot[belong[y]],tree[lroot[belong[y]]].l,rank[v]);
v=fa[y];
}
x=top[belong[u]],y=top[belong[v]];
}
x=max(rank[u],rank[v]);
y=rank[u]+rank[v]-x;
res+=treeqsum(lroot[belong[u]],y,x);
return res; }
int qmax(int u,int v) {
int x=top[belong[u]],y=top[belong[v]],res=-inf;
while(belong[x]!=belong[y]) {
if(dep[x]>dep[y]){
res=max(res,treeqmax(lroot[belong[x]],tree[lroot[belong[x]]].l,rank[u]));
u=fa[x];
}
else {
res=max(res,treeqmax(lroot[belong[y]],tree[lroot[belong[y]]].l,rank[v]));
v=fa[y];
}
x=top[belong[u]],y=top[belong[v]];
}
x=max(rank[u],rank[v]);
y=rank[u]+rank[v]-x;
res=max(res,treeqmax(lroot[belong[u]],y,x));
return res;
}
void prepare() {
int u,v;
scanf("%d",&n);
xiaosiji(i,,n) {
scanf("%d %d",&u,&v);
add(u,v),add(v,u);
}
siji(i,,n) {
scanf("%d",&val[i]);
}
scanf("%d",&q);
dfs1(),dfs2();
}
void solve() {
prepare();
char ord[];
siji(i,,q) {
scanf("%s",ord);
if(ord[]=='C') {
int u;
scanf("%d",&u);
//之前写成scanf("%d%d",&u,&val[u]);应该是因为它获得的是原来的u，可能是个很大的野值
scanf("%d",&val[u]);
change(u);
}
else if(ord[]=='M') {
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",qmax(u,v));
}
else {
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",qsum(u,v));
}
}
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
solve();
}