[ZJOI2018]历史（LCT）

这篇还发了洛谷题解

[Luogu4338] [BZOJ5212]

题解

题意

给出一棵树,给定每一个点的 \(access\) 次数,计算轻重链切换次数的最大值,带修改.

先考虑不带修改怎么做

假设 \(u\) 的子树发生了两次 \(access\) , 那么当且仅当这两次 \(access\) 的点来自 \(u\) 的两个不同的儿子的子树 , 答案才会 \(+1\)

要使得答案最大 , 就是尽量让所有相邻发生的 \(access\) 都来自不同子树

把同类型的数挪到一边就是当 \(2\times h\ge t+1\) 时,答案是 \(2(t-h)\) ,否则是 \(t-1\)

考虑待修改怎么做

令$ f_i$表示 \(i\) 的子树 access 的总次数,如果 \(2f_i\ge f_{fa_i}+1\) 那么连实边 \((i,fa_i)\) 其他的都是虚边

如果把\(i\)子树中的点\(j\)权值加上\(w\) , 则只会影响\(j\)到根节点路径的答案和虚实边关系 ,

因为 \(2(f_i+w)\ge(f_{fa_i}+w)+1\)所以实边还是实边 , 并且答案不会变化

所以我们只需要找到路径上的虚边进行(暴力)修改就好了 , 然后 \(ans+=\) 这个点更新后的答案 \(-\)更新前的答案

这题难在构造实儿子(边)和虚儿子(边) , 注意到虚边只有\(log\)条 , 所以如果转化为

只需要修改虚儿子(边)的信息 , 剩下的通过\(splay\)或者其他一些操作完成就接近正解了

本题中有一个贪心 , 就是子树中\(size>=\)自己的一半的点的贡献的重要性 , 这个点再大也无法影响答案了 , 转化为实儿子(边)对当前点的答案无影响 , 其他的就都定义为轻边

修改是就是\(splay+\)暴力中的分类讨论

注意 : 对于\(rs\)变为虚儿子和\(y\)变为实儿子的判断都要考虑清楚

还有一个特别容易忽视的点 : 为了使崛起过程中战争次数最多 , 尽量要让所有相邻发生的\(access\)都来自不同的子树 , 于是统计\(maxp\)必须考虑\(u\)这个点 , 否则只有\(70\)分

可见复杂的题目一定要对每个子问题都分类清楚 , 特别是 端点 , 边界 , 根节点 , 叶节点 这些地方一般都要特判

否则甚至可能做不出,比如[HDU4035]Maze和[HDU4089]Activation

难题就是简单题的叠加 , \(ZJOI\)的题真神仙

细节详见代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int MAXN=4e5+5;
const int MAXM=8e5+5;

struct Edge{
    int v,next;
}e[MAXM];
int first[MAXN],Ecnt=1;
inline void Add_edge(int u,int v){
    e[++Ecnt]=(Edge){v,first[u]};
    first[u]=Ecnt;
}

int n,m;
LL ans;

namespace LCT{
    LL sum[MAXN],aux[MAXN],val[MAXN];
    int ch[MAXN][2],par[MAXN];
#define ls ch[rt][0]
#define rs ch[rt][1]
    inline bool chk(int x){return ch[par[x]][1]==x;}
    inline bool nrt(int x){return ch[par[x]][0]==x||ch[par[x]][1]==x;}
    inline void pushup(int rt){sum[rt]=sum[ls]+sum[rs]+val[rt]+aux[rt];}//全部加起来
    inline void rotate(int x){
        int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
        ch[y][k]=w,par[w]=y;
        if(nrt(y)) ch[z][chk(y)]=x; par[x]=z;
        ch[x][k^1]=y,par[y]=x;
        pushup(y);pushup(x);
    }
    inline void splay(int x){
        while(nrt(x)){
            int y=par[x];
            if(nrt(y)){
                if(chk(x)==chk(y)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
    }
#undef ls
#undef rs
}using namespace LCT;

//如果按常规写法会错[https://www.luogu.org/recordnew/show/17153906]
//为了使崛起过程中战争次数最多,尽量要让所有相邻发生的access都来自不同的子树
//于是统计maxp必须考虑u这个点
/*inline void dfs(int u,int pre){
    int maxp=0;
    sum[u]=val[u],par[u]=pre;
    for(int i=first[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==pre) continue;
        dfs(v,u);
        sum[u]+=sum[v];
        if(sum[v]>sum[maxp]) maxp=v;
    }
    ans+=min(sum[u]-1,2*(sum[u]-sum[maxp]));
    if(sum[maxp]*2>=sum[u]+1) ch[u][1]=maxp;
    aux[u]=sum[u]-val[u]-sum[ch[u][1]];
}*/

inline void dfs(int u,int pre){
    LL maxp=val[u];int p=0;
    sum[u]=val[u],par[u]=pre;
    for(int i=first[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==pre) continue;
        dfs(v,u);
        sum[u]+=sum[v];
        if(sum[v]>maxp) maxp=sum[p=v];
    }
    ans+=min(sum[u]-1,2*(sum[u]-maxp));
    if(maxp*2>=sum[u]+1) ch[u][1]=p;//存重儿子
    aux[u]=sum[u]-val[u]-sum[ch[u][1]];//虚边的size
}

#define ls ch[u][0]
#define rs ch[u][1]
inline LL calc(int u,LL total,LL weight){
    if(rs) return (total-weight)*2;
    else if(val[u]*2>=total+1) return(total-val[u])*2;
    else return total-1;
}

inline void modify(int u,int w){
    splay(u);
    LL total=sum[u]-sum[ls],weight=sum[rs];
    ans-=calc(u,total,weight);
    sum[u]+=w,val[u]+=w,total+=w;
    if(weight*2<=total) aux[u]+=weight,rs=0;//变为虚边
    ans+=calc(u,total,weight);
    pushup(u);
    //access
	//重点还是维护虚边或虚儿子信息,即access
    int v;
    for(u=par[v=u];u;u=par[v=u]){
        splay(u);
        total=sum[u]-sum[ls],weight=sum[rs];
        ans-=calc(u,total,weight);
        sum[u]+=w,aux[u]+=w,total+=w;//虚边size+=w;
        if(weight*2<=total) aux[u]+=weight,rs=0,weight=0;
        if(sum[v]*2>=total+1) aux[u]-=sum[v],rs=v,weight=sum[v];
        ans+=calc(u,total,weight);
        pushup(u);
    }
}
#undef ls
#undef rs

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) val[i]=read();
    for(int i=1;i<=n-1;i++){
        int x=read(),y=read();
        Add_edge(x,y);
        Add_edge(y,x);
    }
    dfs(1,0);
    printf("%lld\n",ans);
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        modify(x,y);
        printf("%lld\n",ans);
    }
}