BZOJ 1036: [ZJOI2008]树的统计Count-树链剖分(点权)(单点更新、路径节点最值、路径求和)模板，超级认真写了注释啊啊啊
1036: 树的统计Count
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 23015 Solved: 9336
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
Sample Output
4
1
2
2
10
6
5
6
5
16
题意不用翻译，直接就是中文的。
我写这道题的时候感觉自己更智障了，wa了4发，怎么都不知道哪里错了，最后发现是区间查询的时候求和的初始值初始错了(黑脸)
自己的线段树的模板，还是用得顺手，树链剖分的get的两个函数是偷的学长的，学长的代码比有些博客上的写的好，嘻嘻嘻。
感谢学长给我讲了这两个函数，哈哈哈哈哈哈。
代码很认真地写了注释，线段树不理解的再去翻以前写的线段树的博客。
其他就没什么啦，开心.jpg
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int son,siz,fa,dep,top,tip;
struct Edge{//题目的树
int to,next;
}e;
int tot=1,cnt=1,head;
void add(int u,int v)//链式前向星存树(图)
{
e.to=v;
e.next=head;
head=tot++;
}
//树链剖分部分
void dfs1(int u,int father)//第一遍dfs，可以得到当前节点的父亲节点，当前节点的深度，当前节点的重儿子
{
//更新dep，fa，siz数组
siz=1;//保存以u为根的子树节点个数
fa=father;//保存爸爸
dep=dep+1;//记录深度
for(int i=head;i!=-1;i=e.next){//遍历所有和当前节点连接的节点
int v=e.to;
if(v==fa) continue;//如果连接的是当前节点的父亲节点，则不处理
dfs1(v,u);
siz+=siz;//直接子树节点相加，当前节点的size加上子节点的size
if(siz>siz]) son=v;//如果没有设置过重节点son或者子节点v的size大于之前记录的重节点son，进行更新,保存重儿子
}
}
void dfs2(int u,int tp)//第二遍dfs，将各个重节点连接成重链，轻节点连接成轻链，并且将重链(区间)用数据结构(一般是树状数组或者线段树)来维护，并且为每个节点进行编号，其实就是dfs在执行时的顺序(tip数组)，以及当前节点所在链的起点(top数组)还有当前节点在树中的位置(pos)
{
tip=cnt++;//保存树中每个节点剖分以后的新编号(dfs的执行顺序)
top=tp;//保存当前节点所在的链的顶端节点，当前节点的起点
if(son) dfs2(son,tp);//如果当前节点没有处在重链上，则不处理，否则就将这条重链上的所有节点都设置成起始的重节点
for(int i=head;i!=-1;i=e.next){//遍历所有和当前节点连接的节点
int v=e.to;
if(v!=fa&&son!=v) dfs2(v,v);//如果连接节点不是当前节点的重节点并且也不是u的父节点，则将其的top设置成自己，进一步递归
}
}
int w,sum,Max;
//线段树部分
void pushup(int rt)
{
Max=max(Max,Max);
sum=sum+sum;
}
void build(int l,int r,int rt)//线段树建树
{
if(l==r){
sum=Max=w;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int pos,int val,int l,int r,int rt)//单点更新
{
if(l==r){
sum=Max=val;
return;
}
int m=(l+r)>>1;
if(pos<=m) update(pos,val,lson);
else update(pos,val,rson);
pushup(rt);
}
int query_max(int L,int R,int l,int r,int rt)//区间查询最大值
{
if(L<=l&&r<=R){
return Max;
}
int ret=-1<<30;
int m=(l+r)>>1;
if(L<=m) ret=max(ret,query_max(L,R,lson));
if(R> m) ret=max(ret,query_max(L,R,rson));
return ret;
}
int query_sum(int L,int R,int l,int r,int rt)//区间求和
{
if(L<=l&&r<=R){
return sum;
}
ll ret=0;
int m=(l+r)>>1;
if(L<=m) ret+=query_sum(L,R,lson);
if(R> m) ret+=query_sum(L,R,rson);
return ret;
}
void get_sum(int u,int v,int n)//这是最重要的，将树链和线段树联系起来
{
int ans=0;
while(top!=top){//如果两点的top节点不相同
if(dep]<dep]) swap(u,v);//始终让top的深度大于top的，查询深度大的
ans+=query_sum(tip],tip,1,n,1);//查询对应线段树上的区间和，通过tip数组找到对应的位置,找到线段树对应的左右区间l,r，l<=r
v=fa];//将其更改为父亲节点
}
if(dep<dep) swap(u,v);//如果查询的是在线段树一个完整的区间里的一部分
ans+=query_sum(tip,tip,1,n,1);//直接查询就可以
printf("%d\n",ans);
}
void get_max(int u,int v,int n)//同上操作
{
int ans=-1<<30;
while(top!=top){
if(dep]<dep]) swap(u,v);
ans=max(ans,query_max(tip],tip,1,n,1));
v=fa];
}
if(dep<dep) swap(u,v);
ans=max(ans,query_max(tip,tip,1,n,1));
printf("%d\n",ans);
}
int main()
{
int n,q,a,b;
char s;
scanf("%d",&n);
memset(head,-1,sizeof(head));
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);//加边
add(b,a);//加边
}
dfs1(1,1);//第一遍dfs
dfs2(1,1);//第二遍dfs
for(int i=1;i<=n;i++)
scanf("%d",&w]);
build(1,n,1);//建树
scanf("%d",&q);
while(q--){//查询
scanf("%s%d%d",s,&a,&b);
if(s=='M') get_max(a,b,n);
else if(s=='S') get_sum(a,b,n);
else update(tip,b,1,n,1);
}
}
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。
溜了。。。】
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3167982
页:
[1]