随便's Blog

题目：一棵树上有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本身

树链剖分;

每一个点记录子树最大的儿子节点，标记重边。对于每个重边形成的链维护线段树。一棵树上的多个链可以放到一颗线段树中，注意不要弄混就可以了。    Problem: 1036

    User: 1115825064
    Language: C++
    Result: 正确
    Time:2680 ms
    Memory:6472 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
 
using namespace std;
 
const int N=30005;
 
int n;
 
struct D{
    int fa,son,dep,top,size,w;
}a[N];
int tree1[N],pre[N],tot_t=0;
struct L{
    int to,next;
}e[N*2];
int head[N],tot_l=1;
void jial(int u,int v)
{
    e[++tot_l].to=v;e[tot_l].next=head[u];head[u]=tot_l;
}
#define link(x) for(int i=head[x];i;i=e[i].next)
 
struct T{
    int l,r,sum,Max;
}trees[4*N];
 
void dfs1(int wz,int f,int de)//第一次深搜记录父节点·重儿子和深度。
{
    a[wz].fa=f;
    a[wz].dep=de;
    a[wz].size=1;
    int s=1,son=-1e9,p=0;   
    link(wz) if(e[i].to!=f)
    {
        dfs1(e[i].to,wz,de+1);
        a[wz].size+=a[e[i].to].size;
        if(!a[wz].son||a[a[wz].son].size<a[e[i].to].size)
        {
            a[wz].son=e[i].to;
        }
    }
    return ;
}
void dfs2(int wz,int top)//记录重链的最上面的节点。将每条链加入数组中。（要保证同一条链连续）
{
    a[wz].top=top;tree1[wz]=++tot_t;pre[tree1[wz]]=wz;
    if(a[wz].son==0)    return ;
    dfs2(a[wz].son,top);
    link(wz)    if(e[i].to!=a[wz].son&&e[i].to!=a[wz].fa)
        dfs2(e[i].to,e[i].to);
    return ;
}
void build(int i,int l,int r)//建树
{
    trees[i].r=r;
    trees[i].l=l;
    if(l==r)
    {
        trees[i].sum=trees[i].Max=a[pre[l]].w;
        return ;
    }
    build(i*2,l,(l+r)/2);
    build(i*2+1,((l+r)/2)+1,r);
    trees[i].sum=trees[i*2].sum+trees[i*2+1].sum;
    trees[i].Max=max(trees[i*2].Max,trees[i*2+1].Max);
    return ;
}
 
void jia(int wz,int u,int t)
{
     
    if(trees[wz].l==trees[wz].r)
    {
        trees[wz].sum+=t;
        trees[wz].Max+=t;
        return ;
    }
    int mid=(trees[wz].l+trees[wz].r)/2;
    if(u<=mid)
        jia(wz*2,u,t);
    else
        jia(wz*2+1,u,t);
    trees[wz].Max=max(trees[wz*2].Max,trees[wz*2+1].Max);
    trees[wz].sum=trees[wz*2].sum+trees[wz*2+1].sum;
    return ;
}
 
int fi_Max(int i,int ll,int rr)
{
    if(ll<=trees[i].l&&rr>=trees[i].r)
    {
        return trees[i].Max;
    }
    int mid=(trees[i].l+trees[i].r)/2;
    int p=-1e9;
    if(ll<=mid)
        p=fi_Max(i*2,ll,rr);
    if(rr>mid)
        p=max(p,fi_Max(i*2+1,ll,rr));
    return p;
}
int fi_sum(int i,int ll,int rr)
{
    if(ll<=trees[i].l&&rr>=trees[i].r)
    {
        return trees[i].sum;
    }
    int mid=(trees[i].l+trees[i].r)/2;
    int p=0;
    if(ll<=mid)
        p+=fi_sum(i*2,ll,rr);
    if(rr>mid)
        p+=fi_sum(i*2+1,ll,rr);
    return p;
}
 
int q_Max(int u,int v)
{
    int fu=a[u].top,fv=a[v].top;
    if(fu==fv)
    {
        if(tree1[u]>tree1[v]) swap(u,v);
        return fi_Max(1,tree1[u],tree1[v]);
    }
    if(a[fu].dep<a[fv].dep)
    {
        swap(v,u);
        swap(fu,fv);
    }
    int p=q_Max(a[fu].fa,v);
    p=max(p,fi_Max(1,tree1[fu],tree1[u]));
    return p;
     
}
int q_sum(int u,int v)
{
    int fu=a[u].top,fv=a[v].top;
    if(fu==fv)
    {
        if(tree1[u]>tree1[v]) swap(u,v);
        return fi_sum(1,tree1[u],tree1[v]);
    }
        if(a[fu].dep<a[fv].dep)
    {
        swap(v,u);
        swap(fu,fv);
    }
    int p=q_sum(a[fu].fa,v);
    p+=fi_sum(1,tree1[fu],tree1[u]);
    return p;
} 
int main()
{
//  freopen("1.txt","r",stdin);
     
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        jial(u,v);
        jial(v,u);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i].w);
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,1,n);
    char ss[10];
    int Q1,u,v;
    scanf("%d",&Q1);
 
    while(Q1--)
    {
        scanf("%s%d%d",ss,&u,&v);
        if(ss[0]=='C')
        {
            jia(1,tree1[u],v-a[u].w);
            a[u].w=v;
        }
        if(ss[1]=='M')
        {
            printf("%d\n",q_Max(u,v));
        }
        if(ss[1]=='S')
        {
            printf("%d\n",q_sum(u,v));
        }
    }
    return 0;
}

敲了二百多行，写着写着就凌乱了结果交了5遍。感谢这个题，我愉快（chedan）的学会了造数据。orz