rockdu
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<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=30000+100;
int node_w[maxn];
int n;
struct edge
{
int u,v;
int next;
}e[maxn*2];
int head[maxn];
int depth[maxn];
int fa[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
int tid[maxn];
int rank[maxn];//映射tid到图编号
int pos;//tid编号的累加
int edc;
void adde(int u,int v)
{
e[edc].u=u;
e[edc].v=v;
e[edc].next=head[u];
head[u]=edc++;
}
void dfs1(int u,int p)//寻找重儿子
{
depth[u]=depth[p]+1;
siz[u]=1;
fa[u]=p;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(v!=p)
{
dfs1(v,u);
siz[u]+=siz[v];
if(son[u]==-1 || siz[v] > siz[son[u]])
{
son[u]=v;
}
}
}
}
void dfs2(int u,int tp)//链接
{
top[u]=tp;
tid[u]=++pos;
rank[tid[u]]=u;
if(son[u]==-1) //如果为叶子节点
return;
dfs2(son[u],tp);
for(int i=head[u];i!=-1;i=e[i].next)//重新开链
{
int v=e[i].v;
if(v!=son[u] && v!=fa[u])
dfs2(v,v);
}
}
struct seg
{
int l,r;
int sum;
int mx;
}snode[maxn*4];
void pushup(int now)
{
snode[now].sum=snode[now*2].sum+snode[now*2+1].sum;
snode[now].mx=max(snode[now*2].mx,snode[now*2+1].mx);
}
void build_tree(int l,int r,int rt)
{
snode[rt].l=l;snode[rt].r=r;
if(l==r)
{
snode[rt].sum=node_w[rank[l]];//线段树为tid 把tid转换为原编号取权值
snode[rt].mx=node_w[rank[l]];
return;
}
int m=(l+r)/2;
build_tree(l,m,rt*2);
build_tree(m+1,r,rt*2+1);
pushup(rt);
}
void update(int k,int nw,int rt)
{
int tl=snode[rt].l,tr=snode[rt].r;
if(tl==k && tr==k)
{
snode[rt].sum=snode[rt].mx=nw;
return;
}
int mid=(tl+tr)/2;
if(k<=mid) update(k,nw,rt*2);
else update(k,nw,rt*2+1);
pushup(rt);
}
int querymax(int l,int r,int rt)
{
int tl=snode[rt].l,tr=snode[rt].r;
if(tl==l && tr==r)
return snode[rt].mx;
int mid=(tl+tr)/2;
if(r<=mid) return querymax(l,r,rt*2);
else if(l>mid) return querymax(l,r,rt*2+1);
else return max(querymax(l,mid,rt*2),querymax(mid+1,r,rt*2+1));
}
int querysum(int l,int r,int rt)
{
int tl=snode[rt].l,tr=snode[rt].r;
if(tl==l && tr==r)
return snode[rt].sum;
int mid=(tl+tr)/2;
if(r<=mid) return querysum(l,r,rt*2);
else if(l>mid) return querysum(l,r,rt*2+1);
else return querysum(l,mid,rt*2)+querysum(mid+1,r,rt*2+1);
}
int getmax(int a,int b)
{
int ans=-50000;
while(top[a]!=top[b])
{
if(depth[top[a]]<depth[top[b]])
swap(a,b);
ans = max(ans,querymax(tid[top[a]],tid[a],1));
a = fa[top[a]];
}
if(depth[a] > depth[b]) swap(a,b);
return max(ans,querymax(tid[a],tid[b],1));
}
int getsum(int a,int b)
{
int ans=0;
while(top[a]!=top[b])
{
if(depth[top[a]]<depth[top[b]])
swap(a,b);
ans += querysum(tid[top[a]],tid[a],1);
a = fa[top[a]];
}
if(depth[a] > depth[b]) swap(a,b);
return ans+querysum(tid[a],tid[b],1);
}
int main()
{
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
adde(a,b);
adde(b,a);
}
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
node_w[i]=a;
}
dfs1(1,0);
dfs2(1,1);
build_tree(1,n,1);
int t;
scanf("%d",&t);
char comm[20];
while(t--)
{
scanf("%s",comm);
if(strcmp(comm,"QMAX")==0)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",getmax(a,b));
}
if(strcmp(comm,"QSUM")==0)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",getsum(a,b));
}
if(strcmp(comm,"CHANGE")==0)
{
int a,b;
scanf("%d%d",&a,&b);
update(tid[a],b,1);
}
}
return 0;
}
没有帐号? 立即注册