Lvat_s Blog

这是一个坑……得过一阵子再填……

NOIP爆炸了心情不好……

现在打算填坑了。

这题是一个树链剖分，据说LCT也行。但是蒟蒻我啥也不会，于是强行学了一个晚上的树链剖分，总算A掉了这题。

我觉得网上题解已经烂大街了……所以就不发题解了，只（懒）放（癌）代（发）码（作）。

树链剖分+线段树

#include<cstdio>
#include<algorithm>
using namespace std;

int n,w[30005],dep[30005],h[30005],en,data[30005],Q,id[30005],siz[30005],fa[30005],son[30005],top[30005],pre[30005],segn;
char ask[10];

struct Edge{
int b,next;
}e[60005];

struct SegTree{
int l,r,v,sum;
}tr[120005];

void add(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}

void dfs1(int u,int father,int deep){
dep[u]=deep;
fa[u]=father;
son[u]=0;
siz[u]=1;
//printf("ZZT:%d %d %d\n",u,father,deep);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==father)continue;
    dfs1(v,u,deep+1);
    siz[u]+=siz[v];
    if(siz[v]>siz[son[u]]){
        son[u]=v;
    }
}
}

void dfs2(int u,int ux){
top[u]=ux;
id[u]=++segn;
pre[segn]=u;
if(son[u])dfs2(son[u],ux);
else return;
//printf("Tr:%d %d\n",u,ux);
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa[u] || v==son[u])continue;
    dfs2(v,v);
}
}

void Build(int root,int l,int r){
tr[root].l=l;
tr[root].r=r;
if(l==r){
    tr[root].v=data[pre[l]];
    tr[root].sum=data[pre[l]];
    return;
}
int mid=(l+r)/2;
Build(root*2,l,mid);
Build(root*2+1,mid+1,r);
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
}

void Update(int root,int pos,int val){
if(tr[root].l==tr[root].r){
    tr[root].v+=val;
    tr[root].sum+=val;
    //printf("Tx:%d %d %d\n",root,tr[root].v,tr[root].sum);
    return;
}
int mid=(tr[root].l+tr[root].r)/2;
if(pos<=mid)Update(root*2,pos,val);
if(pos>=mid+1)Update(root*2+1,pos,val);
tr[root].sum=tr[root*2].sum+tr[root*2+1].sum;
tr[root].v=max(tr[root*2].v,tr[root*2+1].v);
}

int QuerySum(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].sum;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=0;
if(l<=mid)ans+=QuerySum(root*2,l,r);
if(r>=mid+1)ans+=QuerySum(root*2+1,l,r);
return ans;
}

int QueryMax(int root,int l,int r){
if(tr[root].l>=l && tr[root].r<=r){
    return tr[root].v;
}
int mid=(tr[root].l+tr[root].r)/2;
int ans=-2147483647;
if(l<=mid)ans=max(ans,QueryMax(root*2,l,r));
if(r>=mid+1)ans=max(ans,QueryMax(root*2+1,l,r));
return ans;
}

int AskSum(int u,int v){
int f1=top[u],f2=top[v],ans=0;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans+=QuerySum(1,id[f1],id[u]);
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans+=QuerySum(1,id[u],id[v]);
return ans;
}

int AskMax(int u,int v){
int f1=top[u],f2=top[v],ans=-2147483647;
while(f1!=f2){
    if(dep[f1]<dep[f2]){
        swap(f1,f2);
        swap(u,v);
    }
    ans=max(ans,QueryMax(1,id[f1],id[u]));
    u=fa[f1];
    f1=top[u];
}
if(dep[u]>dep[v]){
    swap(u,v);
}
ans=max(ans,QueryMax(1,id[u],id[v]));
return ans;
}

int main(){
freopen("1036.in","r",stdin);
freopen("1036.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    add(sa,sb);
    add(sb,sa);
}
for(int i=1;i<=n;i++){
    scanf("%d",&data[i]);
}
dfs1(1,0,1);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&Q);
while(Q--){
    int sa,sb;
    scanf("%s %d %d",&ask,&sa,&sb);
    if(ask[0]=='C'){
        Update(1,id[sa],sb-data[sa]);
        data[sa]=sb;
    }
    if(ask[0]=='Q'){
        if(ask[1]=='S'){
            printf("%d\n",AskSum(sa,sb));
        }
        if(ask[1]=='M'){
            printf("%d\n",AskMax(sa,sb));
        }
    }
}
return 0;
}

树链剖分+树状数组（正在填坑中……）

LCT（正在填坑中……）