@xunuo
2017-02-25T13:54:20.000000Z
字数 3713
阅读 978
Time Limit: 10 Sec Memory Limit: 162 MB
树链剖分
一棵树上有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本身
输入的第一行为一个整数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之间。
对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。
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
4
1
2
2
10
6
5
6
5
16
解题思路:
这里要求的有:查询区间最大值:qmax,区间求和:qsum,单点修改change;
1)、查询区间最大值:
如果要查询的u和v不在同一重链上,则先判断top[u]和top[v]的深度,在深度较深的那个重链上直接查询(tid[top[v]],tid[v])区间的最大值后将v跳fa[top[v]]上,直到u,v在同一条重链上,再进行查询这条重链上的最大值;
2)、区间求和:
也是与区间求最大值差不多,若u与v不再同一重链上,则先判断top[u]和top[v]的深度,在深度较深的那个重链上直接求(tid[top[v]],tid[v])区间的和后将v跳fa[top[v]]上,直到u,v在同一条重链上,再进行求这条重链上的和;
3)、单点修改:
当查到这个点时,将它的值改为新的num;按照线段树来~~
完整代码:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 30010
#define inf 0x3f3f3f3f
///dfs1需要维护的:
int sz[N];///记录以u为根节点的子树的节点的个数
int dep[N];///当前节点的深度
int fa[N];///当前节点的父节点
int son[N];///存重儿子
///dfs2
int top[N];///存当前节点所在的链的顶端节点
int tid[N];///每个节点的新编号
int val[N],val1[N];///val[]表示输入的值,val1表示更新节点后对应的值
int clk;///新的编号++clk;
struct node
{
int l,r,maxn,sum;
}t[4*N];
vector<int>g[N];
void dfs1(int u,int f,int d)
{
dep[u]=d;
fa[u]=f;
sz[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==f)
continue;
dfs1(v,u,d+1);
sz[u]+=sz[v];///求以u为顶端节点的节点个数
if(sz[v]>sz[son[u]])///如果v的size比现在有的u的重儿子的size还要大的话,,更新重儿子
son[u]=v;
}
}
void dfs2(int u,int f,int id)
{
top[u]=id;
tid[u]=++clk;///对这棵树重新编号
val1[clk]=val[u];///新的节点对应的val
if(son[u]==0)///跑到叶子节点上了
return;
dfs2(son[u],u,id);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==f||v==son[u])
continue;
dfs2(v,u,v);
}
}
///建树
void build(int id,int l,int r)
{
t[id].l=l;
t[id].r=r;
if(l==r)
{
t[id].maxn=t[id].sum=val1[l];
return;
}
int mid=(l+r)/2;
build(2*id,l,mid);
build(2*id+1,mid+1,r);
t[id].maxn=max(t[2*id].maxn,t[2*id+1].maxn);
t[id].sum=t[2*id].sum+t[2*id+1].sum;
}
///求最大值
int qmax(int id,int l,int r)
{
if(t[id].l==l&&t[id].r==r)
return t[id].maxn;
int mid=(t[id].l+t[id].r)/2;
if(r<=mid)
return qmax(2*id,l,r);
else if(l>mid)
return qmax(2*id+1,l,r);
else
return max(qmax(2*id,l,mid),qmax(2*id+1,mid+1,r));
}
int getmax(int u,int v)
{
int ans=-inf;
while(top[u]!=top[v])///要求的两个点不在同一条重链上
{
if(dep[top[u]]>dep[top[v]])///统一较深的为v
swap(u,v);
ans=max(ans,qmax(1,tid[top[v]],tid[v]));///查询v的顶端节点到v的最大值
v=fa[top[v]];///跳到v的顶端节点的父节点上
}
if(dep[u]>dep[v])///在同一条重链上时,还是以v为较深的点
swap(u,v);
ans=max(ans,qmax(1,tid[u],tid[v]));///在同一条重链上查询最大值
return ans;
}
///求和
int qsum(int id,int l,int r)
{
if(t[id].l==l&&t[id].r==r)
return t[id].sum;
int mid=(t[id].l+t[id].r)/2;
if(r<=mid)
return qsum(2*id,l,r);
else if(l>mid)
return qsum(2*id+1,l,r);
else
return qsum(2*id,l,mid)+qsum(2*id+1,mid+1,r);
}
int getsum(int u,int v)
{
int sum=0;
while(top[u]!=top[v])
{
if(dep[top[u]]>dep[top[v]])
swap(u,v);
sum+=qsum(1,tid[top[v]],tid[v]);
v=fa[top[v]];
}
if(dep[u]>dep[v])
swap(u,v);
sum+=qsum(1,tid[u],tid[v]);
return sum;
}
///权值更改
void change(int id,int x,int num)
{
if(t[id].l==t[id].r)
{
t[id].maxn=t[id].sum=num;///把对应的权值改为新的权值
return;
}
int mid=(t[id].l+t[id].r)/2;
if(x<=mid)
change(2*id,x,num);
else if(x>mid)
change(2*id+1,x,num);
t[id].maxn=max(t[2*id].maxn,t[2*id+1].maxn);///改了之后要重新求一遍最大值和求和了
t[id].sum=t[2*id].sum+t[2*id+1].sum;
}
int main()
{
int n;
scanf("%d",&n);
int a,b;
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
dfs1(1,0,1);
dfs2(1,0,1);
build(1,1,n);
int m;
char s[10];
int x,y;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s%d%d",s,&x,&y);
if(s[1]=='M')
printf("%d\n",getmax(x,y));
else if(s[1]=='S')
printf("%d\n",getsum(x,y));
else if(s[1]=='H')
change(1,tid[x],y);
}
return 0;
}