题解 P4338 【[ZJOI2018]历史】

· · 题解

link-cut-tree好题啊……

我太菜了从去年zjoi咕到现在的一道题

果然zjoi只有数据结构题能做

前置芝士:link-cut-tree(lct)/splay

由于这道题当中我们仅仅是借用了lct的一些思想而已并没有真正的实现make root/access/link/cut操作所以说你不会标准的lct也可以ac本题

(不过话说回来敢刚zjoi的dalao应该会lct吧……)

但是无论如何splay这个数据结构应该是需要的(除非你有精妙的卡常技巧可以让你a了这题)

本题题解

首先有一个简单的结论是:任意时间内一个城市控制的区域一定是一条它到自己的一个祖先的路径

原因也很显然:我们每次更改一个点所属的城市的时候也会同时修改它的所有祖先的控制权，不会出现将一个城市控制的区域被截成两半的情况

那么根据这个结论我们可以将同一个城市控制的区域看成一条重链,各个重链之间通过不是重边的轻边相连

此时一次“崛起”操作的权值就是点i到1路径上的重链条数了,当然前提是i没有控制任何城市,如果i控制了一个城市的话权值就需要减1了

似乎这样计算权值需要分情况讨论还是有点麻烦……让我们尝试继续简化题目给出的条件

我们发现点i到1路径上的重链条数=点i到1路径上的轻边个数+1

但是此时我们依然需要分情况讨论啊……怎么办呢？

有一个性质是当点i至少控制了一个城市时,点i的崛起不会改变点i下面的边的轻重属性

但是如果点i没有控制任何城市的时候，点i的崛起会改变点i下面边的轻重属性

根据这个性质我们可以绕开分情况讨论了,我们此时可以很快的推出一次“崛起”操作的权值是本次操作中的轻重边切换次数

因为点i到1路径上的重边一定不会被切换而轻边一定会被切换并且当点i没有控制任何城市的时候会额外发生一次轻重边切换,所以一次"崛起"操作中的轻重边切换次数就等于点i到1路径上轻边个数+[点i是否没有控制任何城市],这与我们刚才推出来一次"崛起"操作的权值等于点i到1路径上的重链条数-[点i是否控制了至少一个城市]是等价的

既然我们最大化的东西轻重边切换次数之和(一开始没有重边所有边都是轻边)那么问题就会变得稍微好考虑一点,我们考虑每个点对答案的贡献，换句话就是最大化每个点下面的边的轻重边切换次数之和(显然一个点下面最多有一条重边也可能一条重边都没有)

那么我们发现一个点i的轻重边发生切换只会受到来自自己子树的操作的影响

并且发生切换的条件是时间上相邻的两个操作来自于不同的子树或者其中是一个是来自于点i的操作另一个不是来自点i的操作，换句话说和这个操作到底来自于那个点是无关的而仅仅和这个操作来自的子树有关

那么假设我们可以对一个点i安排出一个最优的操作序列，我们就可以在树上dfs，先对当前dfs到的点u的所有子树做出最优的安排，接下来再把这些操作序列按照一种对点u最优的方式"混合"在一起如此这般递归下去我们就可以构造出一个全局最优的的方案了

所以我们现在唯一需要关心的事情就是如何最大化某一个点i的轻重边切换次数，然后我们把每一个点算出来的次数加起来就是我们要的答案

那么这就是一个比较经典的结论了,给你若干种不同颜色的小球要求你把这些小球摆成一列,最大化相邻的不同色球的数目

那么这里有一个结论是我们设球的总数是S最大值是Mx的话答案是

min(S-1,2(S-Mx))

证明的话就是当最大的颜色不过半的时候我们总是可以采取这样的一种贪心策略就是每次都选和上一个球颜色不同的球当中最多的一个球来作为我们放的下一个球，由于最大颜色种类不会过半因此我们总是可以成功构造一种方案出来 此时我们的答案就是S-1

但是如果最大种类过半的话我们会发现刚才的做法是失效的,此时我们的策略就是把这种最大的颜色看成一种颜色然后将其余的所有颜色都插入这种最大的颜色当中,采用这种策略构造出来的结果就是2(S-Mx)了

因此题目让我们计算的式子就是了

\sum_{i=1}^{n}min(S_{i}-1,2(S_{i}-Mx_{i}))

修改相当于将一条以1为端点的链上的S_{i}值加上w

那么我们发现由于我们维护的式子是一个取min的操作,在我们我们取min的分界线就是S+1 \leq 2Mx_{i}如果这个式子为真那么我们的答案将不再是S-1而是2(S-Mx)了

按理说如果是一般的修改我们是没办法维护这个式子的

但是我们的修改有个相当强的性质就是我们每次都给整条链加上一个数字w

注意这里是加而不是减

那么对于一对父子(u,v)如果v是u的带权siz最大的子树的话,v和u的siz同时被加上一个值v依然是u的最大的子树，并且如果v已经已经是u的过半的子树的话，v和u的siz同时加上一个值v依然是u的过半子树

那么我们可以仿照树链剖分中的轻重边定义,定义带权意义下的轻重边

我们定义一个点的所有孩子当中,带权siz最大的点为这个点的重儿子

我们定义如果一个点重儿子的siz已经过半，那么这个点和它的重儿子之间的边为一条重边,其余的边全部是轻边

注意这个定义下一个点和它重儿子之间的边可以是一条轻边

那么我们会有一个比较显然的结论是每经过一条轻边所在子树的带权siz必然翻倍,所以任意一个点到1的路径上至多有log(\sum a_{i})条轻边

让我们接着观察当一对父子(u,v)的siz同时被加上w的时候u的答案会作何变换

如果(u,v)这条边是一条重边的话你会发现答案并不会被改动,同时u的重儿子和轻重边关系也不会被改变

所以答案发生变化的边必然是一条轻边,重儿子和轻重边关系发生改变的边也必然是一条轻边

那么我们只需要找到1~u路径上的所有轻边然后暴力修改一下即可完成答案的维护工作了

问题是我们如何高效找到一条轻边呢？

答案是使用类似于lct一样的数据结构(但是只是一个类似的数据结构并不是lct)

我们保证在同一条重链中的点都在同一个splay当中,并且按照深度排好序,那么我们寻找下一条轻边的操作就是在splay当中查找最小值,将链上的点加上一个值可以通过打标记来实现,将轻边变成重边就是将两个splay接在一起,将重边变成轻边就是一个splay分裂成两个

这样的话我们只需要在若干个splay当中不停的查找最小值就可以完成寻找轻边的任务了

另外一点就是按照我们刚才的定义可能会出现一个点和它的重儿子之间连了一条轻边但是计算答案却按照2(S-Mx)计算的情况,这种情况的出现是因为它自己的点权比较大过半了而不是孩子的点权过大了

那么我们维护这种情况比较麻烦所以我们直接特判掉这种情况

具体来讲我们在检查一条轻边(u,v)是否会成为重边的时候我们先判一下是否出现自己的点权过半这种情况出现了就直接修改答案而不是继续我们的分情况讨论

还有一些需要画图才能说清楚的细节写注释里了

剩下的事情就是写一个比较简易的splay了

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=4*1e5+10;typedef long long ll;
template <class T>
void read(T &x){
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
    if(c == '-') op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
    x = x * 10 + c - '0';
    if(op) x = -x;
}
int n;int m;ll ans;
struct splaytree//简易splay膜板 
{
    int s[N][2];int fa[N];ll val[N];ll add[N];int st[N];int tp;
    inline ll& operator [](const int& x){return val[x];}
    inline int gc(const int& x){return s[fa[x]][1]==x;}
    inline void pd(const int& x)
    {
        if(add[x]==0)return;val[s[x][0]]+=add[x];val[s[x][1]]+=add[x];
        add[s[x][0]]+=add[x];add[s[x][1]]+=add[x];add[x]=0;
    }
    inline void rt(const int& x)
    {
        int d=fa[x];int t=gc(x);s[d][t]=s[x][t^1];fa[s[x][t^1]]=d;
        s[fa[d]][gc(d)]=x;fa[x]=fa[d];s[x][t^1]=d;fa[d]=x;
    }
    inline void rtup(const int& x){rt(gc(x)^gc(fa[x])?x:fa[x]);rt(x);}
    inline void splay(const int& x)
    {
        tp=0;for(int p=x;p;p=fa[p])st[++tp]=p;for(int i=tp;i>=1;i--)pd(st[i]);
        for(;fa[fa[x]]&&fa[x];rtup(x));if(fa[x])rt(x);
    }
    inline int gmi(int x){for(;s[x][0];x=s[x][0]);splay(x);return x;}
    inline void app(const int& u,const int& w){val[u]+=w;add[u]+=w;}
    inline void meg(const int& x,const int& y){s[x][0]=y;fa[y]=x;}
    inline void spi(const int& x){splay(x);fa[s[x][1]]=0;s[x][1]=0;}
}spt;
int v[2*N];int x[2*N];int ct;int al[N];ll w[N];ll nv[N];ll ola[N];int h[N];int fa[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline void dfs(int u,int f)//dfs一遍预处理信息 
{
    for(int i=al[u];i;i=x[i])
        if(v[i]!=f)dfs(v[i],u),w[u]+=w[v[i]],h[u]=(w[h[u]]<w[v[i]])?v[i]:h[u];spt[u]=w[u];
    if((nv[u]<<1)>=w[u]+1)ola[u]=(w[u]-nv[u])<<1;
    else if((w[h[u]]<<1)>=w[u]+1)ola[u]=(w[u]-w[h[u]])<<1,spt.meg(h[u],u);
    else ola[u]=w[u]-1;ans+=ola[u];fa[u]=f;
}
inline void subsolve(int u,int v,ll w)//检查一条轻边是否成为重边 
{
    spt.splay(u);spt.splay(h[u]);spt.app(u,w);ans-=ola[u];//修改 
    if((nv[u]<<1)>=spt[u]+1)ola[u]=(spt[u]-nv[u])<<1;//检查点权是否过半 
    else if(spt[v]>spt[h[u]])//如果成为重儿子 
    {
        h[u]=v;spt.spi(u);//检测是否成为重边 
        if((spt[v]<<1)>=spt[u]+1)ola[u]=(spt[u]-spt[v])<<1,spt.meg(v,u);
        else ola[u]=spt[u]-1;
    }
    else if((spt[h[u]]<<1)>=spt[u]+1)ola[u]=(spt[u]-spt[h[u]])<<1;//检测重边是否合法 
    else ola[u]=spt[u]-1,spt.spi(u);ans+=ola[u];
}
inline void modify(int u,ll w)
{
    ans-=ola[u];nv[u]+=w;//修改 
    if(h[u])//特判u处的轻重边变化 
    {
        spt.splay(u);spt.splay(h[u]);spt.app(u,w);
        if((nv[u]<<1)>=spt[u]+1)ola[u]=(spt[u]-nv[u])<<1,spt.spi(u);
        else if((spt[h[u]]<<1)>=spt[u]+1)ola[u]=(spt[u]-spt[h[u]])<<1;
        else ola[u]=spt[u]-1,spt.spi(u);
    }else spt.splay(u),spt.app(u,w);ans+=ola[u];//向上跳轻边 
    for(int p=spt.gmi(u);fa[p];p=spt.gmi(fa[p]))subsolve(fa[p],p,w);
}
int main()
{
    read(n);read(m);
    for(int i=1;i<=n;i++)read(w[i]);
    for(int i=1;i<=n;i++)nv[i]=w[i];
    for(int i=1,u,v;i<n;i++)read(u),read(v),add(u,v),add(v,u);dfs(1,0);
    printf("%lld\n",ans);
    for(int i=1,u,w;i<=m;i++)
    {read(u),read(w),modify(u,w),printf("%lld\n",ans);}return 0;//拜拜程序~ 
}