BZOJ5212 ZJOI2018历史（LCT）

　　首先相当于最大化access的轻重边交换次数。

　　考虑每个点作为战场（而不是每个点所代表的国家与其他国家交战）对答案的贡献，显然每次产生贡献都是该点的子树内（包括自身）此次access的点与上次access的点在该点不同儿子的子树内。假设得到了最后的崛起序列，可以发现相互不包含的子树的贡献是相互独立的，只是内部交换而不交换他们的相对顺序，对答案没有任何影响。

　　那么现在只需要考虑最大化某点的贡献，显然应该让不同儿子的子树内的点尽量交替access。设各点子树的Σa_i为s_i，那么当不存在2s_son>s_i时，该点贡献为s_i-1，否则为2(s_i-max{s_son})。于是如果没有修改，对每个子树求出s就能计算答案了。

　　接下来考虑怎么修改。显然修改某点会影响该点到根的路径上的所有点的贡献。因为贡献与2s_son>s_i的儿子有特殊的关系，考虑将其视为preferred child，把子树根与该儿子的边设为重边，如果不存在或根自身就是最大的就与儿子全部连轻边。同时注意到修改只会使某点的a_i增加，如果其本来就是preferred child，修改后仍然是，并且可以发现这不会对答案造成影响；如果不是的话可能会存在轻重边切换的情况，其自身变为preferred child，但无论如何这说明这棵子树原来的s_son不足其父亲s_i的一半，而这显然只能存在log次。所以用一棵不会动的LCT做一个真正的access就能修改了，可以打个lazy避免维护子树。感觉有一堆情况事实上最后也没啥要讨论的。

　　虽然写了一年但是1A感觉爽爆啊？

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cassert>

using namespace std;

#define ll long long

#define N 400010

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

#define lself tree[tree[k].fa].ch[0]

#define rself tree[tree[k].fa].ch[1]

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,p[N],t;

ll ans;

struct data{int to,nxt;

}edge[N<<];

struct data2{int ch[],fa;ll x,s,lazy,ans;

}tree[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

void dfs(int k,int from)

{

    tree[k].s=tree[k].x;ll mx=tree[k].x;

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        tree[edge[i].to].fa=k;

        dfs(edge[i].to,k);

        tree[k].s+=tree[edge[i].to].s;

        mx=max(mx,tree[edge[i].to].s);

    }

    if (*mx<=tree[k].s) tree[k].ans=tree[k].s-;

    else

    {

        tree[k].ans+=tree[k].s-mx<<;

        for (int i=p[k];i;i=edge[i].nxt)

        if (edge[i].to!=from&&tree[edge[i].to].s==mx) {tree[k].ch[]=edge[i].to;break;}

    }

    ans+=tree[k].ans;

}

void add(int k,ll x){if (k) tree[k].s+=x,tree[k].lazy+=x;}

void down(int k){if (tree[k].lazy) add(lson,tree[k].lazy),add(rson,tree[k].lazy),tree[k].lazy=;}

int whichson(int k){return rself==k;}

bool isroot(int k){return lself!=k&&rself!=k;}

void push(int k){if (!isroot(k)) push(tree[k].fa);down(k);}

void move(int k)

{

    int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k);

    if (!isroot(fa)) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf;

    tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa;

    tree[k].ch[!p]=fa,tree[fa].fa=k;

}

void splay(int k)

{

    push(k);

    while (!isroot(k))

    {

        int fa=tree[k].fa;

        if (!isroot(fa))

            if (whichson(fa)^whichson(k)) move(k);

            else move(fa);

        move(k);

    }

}

void access(int k,int x)

{

    tree[k].x+=x;

    for (int t=;k;)

    {

        splay(k);

        if (rson)

        {

            int p=rson;for (;tree[p].ch[];p=tree[p].ch[]) down(p);

            splay(p);

            while (!isroot(k)) move(k);

        }

        tree[k].s+=x;

        ans-=tree[k].ans;

        if ((tree[rson].s<<)<=tree[k].s) rson=;

        if ((tree[t].s<<)>tree[k].s) rson=t,tree[k].ans=tree[k].s-tree[t].s<<;

        else if ((tree[k].x<<)>tree[k].s) tree[k].ans=tree[k].s-tree[k].x<<;

        else if ((tree[rson].s<<)>tree[k].s) tree[k].ans=tree[k].s-tree[rson].s<<;

        else tree[k].ans=tree[k].s-;

        ans+=tree[k].ans;

        add(lson,x);

        for (;lson;k=lson) down(k);

        splay(k);

        t=k;k=tree[k].fa;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5212.in","r",stdin);

    freopen("bzoj5212.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) tree[i].x=read();

    for (int i=;i<n;i++)

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

    }

    dfs(,);cout<<ans<<endl;

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read();

        access(x,y);

        printf(LL,ans);

    }

    return ;

}

巴特西

BZOJ5212 ZJOI2018历史（LCT）

最新文章

热门文章