P3345 [ZJOI2015]幻想乡战略游戏

传送门

考虑先随便找一个点作为根，然后再慢慢移动根，这样一步步走到最优的点

设 $sum[x]$ 表示节点 $x$ 的子树的军队数，$len(x,y)$ 表示 $x,y$ 之间边的长度

那么对于根节点 $x$ 的一个儿子 $v$，考虑把儿子搞为根时，代价的改变量

$v$ 的子树内的军队消耗减少，共减少了 $sum[v]\cdot len(x,v)$

$v$ 的子树外的军队消耗增加，即根节点 $x$ 的子树内除了 $v$ 子树的军队消耗增加

代价增加了 $(sum[x]-sum[v])\cdot len(x,y)$

如果儿子比父亲优，那么整理可得 $2sum[v]>sum[x]$，显然满足条件的 $v$ 只有一个

此时如果没有满足的 $v$ ，那么 $x$ 就是最优点，否则最优点在 $x$ 的子树内

如果每次都一个一个儿子跳下去，显然会GG

但是因为最优点在子树内所以可以考虑在点分树上跳

我们需要维护两个东西 : $S[x],Sf[x]$，分别表示节点 $x$的点分树子树到 $x$ 的总代价，节点 $x$ 的点分树子树到 $x$ 在点分树父亲 $Fa[x]$ 的总代价

那么计算一个节点 $x$ 的总消耗就考虑一直往 $Fa$ 跳，每次跳完就考虑这一段产生的代价

设当前跳到了节点 $now$

那么十分显然 $Fa[now]$ 的点分树子树不包括 $now$ 的点分树子树的部分新产生的代价为 $S[Fa[now]]-Sf[now]+(sum[Fa[now]]-sum[now])\cdot dis(Fa[now],x)$

（$dis(x,y)$表示节点 $x,y$ 在原树上的距离，注意此时 $sum[x]$ 表示节点 $x$ 的点分树子树军队总数）

我们可以用 RMQ 求 LCA 来 $O(1)$ 求出两点间的距离

至于修改操作也在点分树上直接维护就好了

注意$long long$，代码有注释

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

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

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

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+,INF=1e9+;

int fir[N],from[N],to[N],val[N],cntt;

inline void add(int &a,int &b,int &c)

{

    from[++cntt]=fir[a]; fir[a]=cntt;

    to[cntt]=b; val[cntt]=c;

}

int n,m,tot,rt;

int sz[N],mx[N],Fa[N];

vector <int> V[N],G[N];//存点分树

bool vis[N];

void find_rt(int x,int fa)

{

    sz[x]=; mx[x]=;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i]; if(v==fa||vis[v]) continue;

        find_rt(v,x); sz[x]+=sz[v];

        mx[x]=max(mx[x],sz[v]);

    }

    mx[x]=max(mx[x],tot-sz[x]);

    if(mx[x]<mx[rt]) rt=x;

}

void build(int x)//建点分树

{

    vis[x]=;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i]; if(vis[v]) continue;

        tot=sz[v]; rt=; find_rt(v,);

        V[x].push_back(rt); G[x].push_back(v);

        Fa[rt]=x;  build(rt);

    }

}

int st[N],dfn[N],pos[N],dis[N],Top,dfs_clock,f[N][],Log[N];//维护RMQ求LCA维护dis

void dfs(int x,int fa)

{

    dfn[x]=++dfs_clock; st[++Top]=x; pos[x]=Top;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i]; if(v==fa) continue;

        dis[v]=dis[x]+val[i]; dfs(v,x);

        st[++Top]=x;

    }

}

void pre()

{

    Log[]=-; for(int i=;i<=Top;i++) Log[i]=Log[i>>]+;

    for(int i=;i<=Top;i++) f[i][]=st[i];

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

        for(int j=;j+(<<i-)<=Top;j++)

        {

            if(dfn[f[j][i-]]<dfn[ f[j+(<<i-)][i-] ]) f[j][i]=f[j][i-];

            else f[j][i]=f[j+(<<i-)][i-];

        }

}

inline int LCA(int x,int y)

{

    int l=pos[x],r=pos[y]; if(l>r) swap(l,r);

    int k=Log[r-l+];

    if(dfn[f[l][k]]<dfn[f[r-(<<k)+][k]]) return f[l][k];

    return f[r-(<<k)+][k];

}

inline int Dis(int x,int y) { return dis[x]+dis[y]-*dis[LCA(x,y)]; }

ll sum[N],S[N],Sf[N];//注意long long

inline void change(int x,int y)//修改操作

{

    sum[x]+=y;

    for(int now=x;Fa[now];now=Fa[now])//在点分树上跳

    {

        int d=Dis(x,Fa[now]);

        Sf[now]+=1ll*d*y;

        S[Fa[now]]+=1ll*d*y;

        sum[Fa[now]]+=y;

    }

}

inline ll calc(int x)//计算以x为根的花费

{

    ll res=S[x];

    for(int now=x;Fa[now];now=Fa[now])

    {

        int d=Dis(x,Fa[now]);

        res+=S[Fa[now]]-Sf[now]+(sum[Fa[now]]-sum[now])*d;

    }

    return res;

}

ll query(int x)//点分树上暴力dfs找最优解

{

    ll res=calc(x); int len=V[x].size();

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

    {

        ll t=calc(G[x][i]);//注意是算G[x][i]

        if(t<res) return query(V[x][i]);//注意是往V[x][i]跳

    }

    return res;

}

int main()

{

    int a,b,c,RT;

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

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

    {

        a=read(),b=read(),c=read();

        add(a,b,c); add(b,a,c);

    }

    tot=n; mx[]=INF;

    find_rt(,); RT=rt; build(rt);

    dfs(,); pre();

    while(m--)

    {

        a=read(); b=read();

        change(a,b);

        printf("%lld\n",query(RT));

    }

    return ;

}

巴特西

P3345 [ZJOI2015]幻想乡战略游戏

最新文章

热门文章