Luogu 2590 [ZJOI2008]树的统计 / HYSBZ 1036 [ZJOI2008]树的统计Count （树链剖分，LCA，线段树）

Luogu 2590 [ZJOI2008]树的统计 / HYSBZ 1036 [ZJOI2008]树的统计Count （树链剖分，LCA，线段树）

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”的形式给出。

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

Http

Luogu:https://www.luogu.org/problem/show?pid=2590

HYSBZ:http://www.lydsy.com/JudgeOnline/problem.php?id=1036

Source

树链剖分，最近公共祖先LCA，线段树

解决思路

这是一道树链剖分入门题。

考虑将树按照子树大小剖分成轻链和重链，然后用线段树来维护区间和和区间最大值。

需要注意的是，在树上进行链的跳转时，使用原编号，而若要用线段树查询或修改线段树时，要使用线段树中的编号（即第2次dfs中给点新分配的编号）

代码

#include

#include

#include

#include

#include

using namespace std;

#define ll long long

const int maxN=350000;

const int inf=2147483647;

class Edge//边

{

public:

int u,v,nex;

};

class SegmentTree//线段树

{

public:

ll mx,sum;//维护最大值和区间和

SegmentTree()

{

mx=0;

sum=0;

}

};

class Tree_Chain//树链剖分中需要维护的一些值

{

public:

int f,sz,top,hson,depth;//父节点，大小，向上跳的最高位置，重儿子，深度

};

int n;

//Tree 原树的一些数据

int cnt;

int Head[maxN];

Edge E[maxN*2];

ll W[maxN];//点权

Tree_Chain T[maxN];//树链剖分维护的值

int dfn[maxN];//记录树链剖分后的点的新编号（按照先重链再轻链）

SegmentTree Seg[maxN*4];//线段树

void Add_Edge(int u,int v);

//Tree_Chain

void dfs1(int u,int father);//第一遍dfs求出T中的一些数据

void dfs2(int u,int Top);//第二遍dfs构造Top和分配新编号

ll LCA_sum(int u,int v);//求解区间和

ll LCA_max(int u,int v);//求解区间最大值

//SegmentTree

void Update(int l,int r,int now,int pos,int key);//线段树单点更新

ll Query_sum(int l,int r,int now,int ql,int qr);//查询区间和

ll Query_max(int l,int r,int now,int ql,int qr);//查询区间最大值

int main()

{

cnt=0;

memset(Head,-1,sizeof(Head));

scanf("%d",&n);

for (int i=1;i

{

int u,v;

scanf("%d%d",&u,&v);

Add_Edge(u,v);

Add_Edge(v,u);

}

T[1].f=0;//默认1为根节点

T[1].depth=1;

dfs1(1,1);//第一遍dfs

cnt=0;//标号置为0

dfs2(1,1);//第二遍dfs

for (int i=1;i<=n;i++)//输入点权

scanf("%lld",&W[i]);

for (int i=1;i<=n;i++)

Update(1,n,1,dfn[i],W[i]);//将点权按照新编号放入线段树

int qus;

scanf("%d",&qus);

while (qus--)//处理操作

{

char str[10];

scanf("%s",str);

if (str[0]=='Q')

{

int u,v;

scanf("%d%d",&u,&v);

if (str[1]=='M')

printf("%lld\n",LCA_max(u,v));//查询最大值

else

printf("%lld\n",LCA_sum(u,v));//查询和

}

else

{

int pos,key;

scanf("%d%d",&pos,&key);

pos=dfn[pos];

Update(1,n,1,pos,key);//单点修改

}

}

return 0;

}

void Add_Edge(int u,int v)//在图中加一条边

{

cnt++;

E[cnt].nex=Head[u];

Head[u]=cnt;

E[cnt].u=u;

E[cnt].v=v;

return;

}

void dfs1(int u,int father)//第一遍dfs

{

T[u].sz=1;//初始化基本信息

T[u].hson=0;

for (int i=Head[u];i!=-1;i=E[i].nex)

{

int v=E[i].v;

if (v==father)

continue;

T[v].f=u;//将子节点信息更新

T[v].depth=T[u].depth+1;

dfs1(v,u);

T[u].sz=T[u].sz+T[v].sz;

if ((T[u].hson==0)||(T[T[u].hson].sz

T[u].hson=v;

}

return;

}

void dfs2(int u,int Top)//第二遍dfs，Top是当前传下来的能到达的重链顶端，当u==Top时，为轻链

{

cnt++;

dfn[u]=cnt;//分配新编号

T[u].top=Top;//分配Top

if (T[u].hson==0)//没有重儿子，说明到了叶子节点

return;

dfs2(T[u].hson,Top);//让重儿子继承重链

for (int i=Head[u];i!=-1;i=E[i].nex)

{

int v=E[i].v;

if ((v==T[u].f)||(v==T[u].hson))

continue;

dfs2(v,v);//其他儿子开轻链

}

return;

}

ll LCA_max(int u,int v)//求解u到v路径上的最大点权

{

ll mx=-inf;

while (T[u].top!=T[v].top)

{

if (T[T[u].top].depth

swap(u,v);

mx=max(mx,Query_max(1,n,1,dfn[T[u].top],dfn[u]));//让深度大的向上跳，注意这里要转成线段树中的编号

u=T[T[u].top].f;

}

if (dfn[v]

swap(u,v);

mx=max(mx,Query_max(1,n,1,dfn[u],dfn[v]));//查询链

return mx;

}

ll LCA_sum(int u,int v)//求解u到v上的点权之和，与上面基本一样

{

ll sum=0;

while (T[u].top!=T[v].top)

{

if (T[T[u].top].depth

swap(u,v);

sum=sum+Query_sum(1,n,1,dfn[T[u].top],dfn[u]);

u=T[T[u].top].f;

}

if (dfn[v]

swap(u,v);

sum=sum+Query_sum(1,n,1,dfn[u],dfn[v]);

return sum;

}

void Update(int l,int r,int now,int pos,int key)//线段树单点修改

{

if (l==r)

{

Seg[now].mx=Seg[now].sum=key;

return;

}

int mid=(l+r)/2;

if (pos<=mid)

Update(l,mid,now*2,pos,key);

if (pos>=mid+1)

Update(mid+1,r,now*2+1,pos,key);

Seg[now].sum=Seg[now*2].sum+Seg[now*2+1].sum;

Seg[now].mx=max(Seg[now*2].mx,Seg[now*2+1].mx);

return;

}

ll Query_sum(int l,int r,int now,int ql,int qr)//线段树查询区间和

{

if ((l==ql)&&(r==qr))

return Seg[now].sum;

int mid=(l+r)/2;

if (qr<=mid)

return Query_sum(l,mid,now*2,ql,qr);

else if (ql>=mid+1)

return Query_sum(mid+1,r,now*2+1,ql,qr);

else

return Query_sum(l,mid,now*2,ql,mid)+Query_sum(mid+1,r,now*2+1,mid+1,qr);

}

ll Query_max(int l,int r,int now,int ql,int qr)//线段树查询区间最大值

{

if ((l==ql)&&(r==qr))

return Seg[now].mx;

int mid=(l+r)/2;

if (qr<=mid)

return Query_max(l,mid,now*2,ql,qr);

if (ql>=mid+1)

return Query_max(mid+1,r,now*2+1,ql,qr);

return max(Query_max(l,mid,now*2,ql,mid),Query_max(mid+1,r,now*2+1,mid+1,qr));

}