以下是我今天解题的题解报告:
[1]树的统计
题目描述
一棵树上有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
思路:
这是一个模板,在跑完DFS之后对已有的数据建一个线段树:
要求区间求和,区间求最大值,单点更新。
操作为1,就输出区间[x,y]的总和j
具体看代码,

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define xx 100005
int size[xx], wson[xx], dep[xx], fa[xx], top[xx];
//x节点的节点数,重儿子,深度,父亲,x所在重链的链头。 
int tops[xx], pre[xx], cnt, ta;//dfs序,dfs序的反映射,cnt,ta计数用。 
int w[4*xx], n, q; //节点权值,节点数,操作数。 
string ad;//操作指令。 
struct re
{
    int next,head,t;
}e[xx<<2];//存图 。 
struct ak
{
    int sum,maxv,r,l;
}tree[xx<<2];//存线段树。 
 
void add(int x,int y)
{
    e[++ta].t=y;e[ta].next=e[x].head;e[x].head=ta;
    e[++ta].t=x;e[ta].next=e[y].head;e[y].head=ta;//建图。
} 
 
void dfs1(int now,int f)
{
    size[now]=1;//dfs每个点的子节点数,深度,重链所在节点的重儿子, 
    for(int i=e[now].head;i;i=e[i].next)
    {
        int go=e[i].t;
        if(go!=f)//因为是双向图,所以要防止无限递归爆栈。 
        {
            dep[go]=dep[now]+1;fa[go]=now;
            dfs1(go,now);
            size[now]+=size[go];
            if(size[go]>size[wson[now]])
            wson[now]=go;
            //如果go的子节点数比父亲当前的重儿子子节点数多,则go替换成为重儿子。 
        }
    }
}
void dfs2(int now,int tp)
{
 
    tops[now]=++cnt; pre[cnt]=now; top[now]=tp;//记录所有节点的dfs序及其反映射。 
    if(wson[now]) dfs2( wson[now],tp );//如果有重儿子则继续编号。 
    for(int i=e[now].head;i;i=e[i].next)
    {
        int go=e[i].t;
        if(go!=fa[now]&&go!=wson[now])
        {
            dfs2(go,go);//再去拉伸除重儿子外的节点的子节点下的重链。 
        }
    }
}
void build(int d,int l,int r)
{
 
    int mid=(l+r)/2;//线段树建树(dfs序的线段树)。 
    tree[d].l=l;tree[d].r=r;
    if(l==r)
    {
        tree[d].sum=tree[d].maxv=w[pre[l]];//不同点在是w[pre[l]]不是w[l]。 
        return;
    }
    build(d*2,l,mid);build(d*2+1,mid+1,r);
    tree[d].sum=tree[d*2].sum+tree[d*2+1].sum;
    tree[d].maxv=max(tree[d*2].maxv,tree[d*2+1].maxv);
}
void update(int d,int x,int z)
{
//线段树单点修改操作。 
 
    int mid=(tree[d].l +tree[d].r )/2;
    if(tree[d].l==tree[d].r)
    {
        tree[d].sum=tree[d].maxv=z;
        return;
    }
    if(x>mid)
    {
        update(d*2+1,x,z);
    }
    else
    {
        update(d*2,x,z);
    }
    tree[d].sum=tree[d*2].sum+tree[d*2+1].sum;
    tree[d].maxv=max(tree[d*2].maxv,tree[d*2+1].maxv);
    //修改受影响区间的sum和maxv。 
}
 
int treesum(int d,int l,int r,int ql,int qr)
{
 
    int mid=(l+r)/2,ans=0;
    if (ql<=l&&r<=qr)return tree[d].sum;
    if (ql<=mid)ans+=treesum(d*2,l,mid,ql,qr);
    if (qr>mid)ans+=treesum(d*2+1,mid+1,r,ql,qr);
    return ans;
}
int treemaxv(int d,int ql,int qr)
{
 
    int mid=(tree[d].l+tree[d].r)/2,ans=-1000000;
    if (ql<=tree[d].l&&tree[d].r<=qr)return tree[d].maxv;
    if (ql<=mid)ans=max(ans,treemaxv(d*2,ql,qr));
    if (qr>mid)ans=max(ans,treemaxv(d*2+1,ql,qr));
    return ans;
}
 
int psum(int x,int y)
{
 
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);//使x存深度较大的节点的序号(是原序号,不是dfs序)。 
        ans+=treesum(1,1,n,tops[top[x]],tops[x]);
        //寻找x顶节点dfs序到x节点dfs序的区间和。 
        x=fa[top[x]];//x赋值为根节点的父亲节点。 
    }
    if(dep[x]<dep[y]) swap(x,y);
    ans+=treesum(1,1,n,tops[y],tops[x]);//如果根节点相同,直接计算。 
    return ans;
}
int pmax(int x,int y )
{
 
    int ans=-1000000000;//和求和代码很相似,不解释了。 
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=max(ans,treemaxv(1,tops[top[x]],tops[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y]) swap(x,y);
    ans=max(ans,treemaxv(1,tops[y],tops[x]));
    return ans;
}
int main()
{
 
    cin>>n;
    for(int i=1;i<=n-1;++i)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);//函数直接写的存双向图。 
    }
    for(int i=1;i<=n;++i)
    {
        cin>>w[i];
    }
    dep[1]=1;fa[1]=1;dfs1(1,-1);dfs2(1,1);build(1,1,n);
    cin>>q;
    for(int i=1;i<=q;++i)
    {
        int x,y;cin>>ad;cin>>x>>y;
        if(ad[1]=='H') update(1,tops[x],y);
        if(ad[1]=='M') cout<<pmax(x,y)<<'\n';
        if(ad[1]=='S') cout<<psum(x,y)<<'\n';
    }
    return 0;
}