BZOJ 1036: [ZJOI2008]树的统计Count-树链剖分(点权)(单点更新、路径节点最值、路径求和)模板，超级认真写了注释啊啊啊

POOPE

1036: [ZJOI2008]树的统计Count
Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 23015  Solved: 9336
[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

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[maxn],siz[maxn],fa[maxn],dep[maxn],top[maxn],tip[maxn];
struct Edge{//题目的树
  int to,next;
}e[maxn<<1];
int tot=1,cnt=1,head[maxn];
void add(int u,int v)//链式前向星存树(图)
{
  e[tot].to=v;
  e[tot].next=head[u];
  head[u]=tot++;
}
//树链剖分部分
void dfs1(int u,int father)//第一遍dfs，可以得到当前节点的父亲节点，当前节点的深度，当前节点的重儿子
{
  //更新dep，fa，siz数组
  siz[u]=1;//保存以u为根的子树节点个数
  fa[u]=father;//保存爸爸
  dep[u]=dep[father]+1;//记录深度
  for(int i=head[u];i!=-1;i=e[i].next){//遍历所有和当前节点连接的节点
    int v=e[i].to;
    if(v==fa[u]) continue;//如果连接的是当前节点的父亲节点，则不处理
    dfs1(v,u);
    siz[u]+=siz[v];//直接子树节点相加，当前节点的size加上子节点的size
    if(siz[v]>siz[son[u]]) son[u]=v;//如果没有设置过重节点son或者子节点v的size大于之前记录的重节点son，进行更新,保存重儿子
  }
}
void dfs2(int u,int tp)//第二遍dfs，将各个重节点连接成重链，轻节点连接成轻链，并且将重链(区间)用数据结构(一般是树状数组或者线段树)来维护，并且为每个节点进行编号，其实就是dfs在执行时的顺序(tip数组)，以及当前节点所在链的起点(top数组)还有当前节点在树中的位置(pos)
{
  tip[u]=cnt++;//保存树中每个节点剖分以后的新编号(dfs的执行顺序)
  top[u]=tp;//保存当前节点所在的链的顶端节点，当前节点的起点
  if(son[u]) dfs2(son[u],tp);//如果当前节点没有处在重链上，则不处理，否则就将这条重链上的所有节点都设置成起始的重节点
  for(int i=head[u];i!=-1;i=e[i].next){//遍历所有和当前节点连接的节点
    int v=e[i].to;
    if(v!=fa[u]&&son[u]!=v) dfs2(v,v);//如果连接节点不是当前节点的重节点并且也不是u的父节点，则将其的top设置成自己，进一步递归
  }
}
int w[maxn<<2],sum[maxn<<2],Max[maxn];
//线段树部分
void pushup(int rt)
{
  Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
  sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)//线段树建树
{
  if(l==r){
    sum[rt]=Max[rt]=w[l];
    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[rt]=Max[rt]=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[rt];
  }
  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[rt];
  }
  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[u]!=top[v]){//如果两点的top节点不相同
    if(dep[top[v]]<dep[top[u]]) swap(u,v);//始终让top[v]的深度大于top[u]的，查询深度大的
    ans+=query_sum(tip[top[v]],tip[v],1,n,1);//查询对应线段树上的区间和，通过tip数组找到对应的位置,找到线段树对应的左右区间l,r，l<=r
    v=fa[top[v]];//将其更改为父亲节点
  }
  if(dep[u]<dep[v]) swap(u,v);//如果查询的是在线段树一个完整的区间里的一部分
  ans+=query_sum(tip[v],tip[u],1,n,1);//直接查询就可以
  printf("%d\n",ans);
}
void get_max(int u,int v,int n)//同上操作
{
  int ans=-1<<30;
  while(top[u]!=top[v]){
    if(dep[top[v]]<dep[top[u]]) swap(u,v);
    ans=max(ans,query_max(tip[top[v]],tip[v],1,n,1));
    v=fa[top[v]];
  }
  if(dep[u]<dep[v]) swap(u,v);
  ans=max(ans,query_max(tip[v],tip[u],1,n,1));
  printf("%d\n",ans);
}
int main()
{
  int n,q,a,b;
  char s[15];
  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[tip[i]]);
  build(1,n,1);//建树
  scanf("%d",&q);
  while(q--){//查询
    scanf("%s%d%d",s,&a,&b);
    if(s[1]=='M') get_max(a,b,n);
    else if(s[1]=='S') get_sum(a,b,n);
    else update(tip[a],b,1,n,1);
  }
}

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。
溜了。。。】