题解 P3345 【[ZJOI2015]幻想乡战略游戏】

· · 题解

很久没有被题目恶心得欲仙欲死了

于是今天找了个虐

正文

整理好思路其实这题是要比捉迷藏、Qtree4好写的

Step1

建好点分树以及打好树剖（用来求两点距离）

Step2

维护三个东西就很好计算以指定的某个点为补给站的答案了

  d[x]表示点分树上以x为根的子树的兵队总数
  val[x]表示点分树上以x为根的子树的兵队到达x的代价和
  tofa[x]表示点分树上以x为根的子树的兵队到达x的父亲的代价和

于是具体操作在Calc函数中，有详细解释

Step3

具体代码流程

1.建好点分树

2.修改某个点，暴跳点分树的父亲对应修改三个值

3.从点分树根开始查询，找到真正的带权重心后返回答案（Query函数有详细注释）

注意事项

1.要开long long （反正有6秒你开gedit就可以把int全部换成long long）

2.贪心跳带权重心，你此时在x点，点分树上x的儿子有y，你看x要不要跳到y，需要检查的是y的分治区域与x直接相连的那个点（near[y]）的答案是否比x的小，而不是检查y的

3.本人太菜在Getroot没有判断vis而TLE了一次

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#define ll long long
using namespace std;
ll read()
{
    char ch=getchar();ll h=0,t=1;
    while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
    return h*t;
}
const ll N=100100;
struct edge{ll next,to,w;}a[N<<1];
ll n,q,head[N],cnt,rt,mx[N],siz[N],fa[N],vis[N],sum;
ll d[N],val[N],tofa[N],Root,near[N];
vector<int> erz[N];
/*
  d[x]表示点分树上以x为根的子树的兵队总数
  val[x]表示点分树上以x为根的子树的兵队到达x的代价和
  tofa[x]表示点分树上以x为根的子树的兵队到达x的父亲的代价和
  erz[x]记录点分树上x的儿子
  near[x]表示x的分治区域与x点分树父亲的相邻结点
 */
void Max(ll &a,ll b) {if(b>a) a=b;}
void link(ll x,ll y,ll w)
{
    a[++cnt]=(edge){head[x],y,w};head[x]=cnt;
    a[++cnt]=(edge){head[y],x,w};head[y]=cnt;
}
namespace sp
{
    ll siz[N],dep[N],son[N],top[N],tot,dfn[N],fa[N];
    void dfs1(ll x)
    {
        for(ll i=head[x];i;i=a[i].next)
        {
            ll R=a[i].to;if(R==fa[x]) continue;
            fa[R]=x;siz[R]=1;dep[R]=dep[x]+a[i].w;
            dfs1(R);siz[x]+=siz[R];
            if(siz[R]>siz[son[x]]) son[x]=R;
        }
    }
    void dfs2(ll x)
    {
        top[x]=x;dfn[x]=++tot;
        if(son[fa[x]]==x) top[x]=top[fa[x]];
        if(son[x]) dfs2(son[x]);
        for(ll i=head[x];i;i=a[i].next)
            if(a[i].to!=son[x]&&a[i].to!=fa[x]) dfs2(a[i].to);
    }
    ll LCA(ll x,ll y)
    {
        while(top[x]^top[y])
        {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            x=fa[top[x]];
        }
        return dep[x]<dep[y]?x:y;
    }
    ll Dis(ll x,ll y) {return dep[x]+dep[y]-2*dep[LCA(x,y)];}
}
void Getroot(ll x,ll f)
{
    siz[x]=1;mx[x]=0;
    for(ll i=head[x];i;i=a[i].next)
    {
        ll R=a[i].to;if(R==f||vis[R]) continue;
        Getroot(R,x);siz[x]+=siz[R];
        Max(mx[x],siz[R]);
    }
    Max(mx[x],sum-siz[x]);
    if(mx[x]<mx[rt]) rt=x;
}
void solve(ll x,ll f)
{
    vis[x]=1;
    for(ll i=head[x],tt=sum;i;i=a[i].next)
    {
        ll R=a[i].to;if(vis[R]) continue;
        rt=0;sum=siz[R]>siz[x]?tt-siz[x]:siz[R];
        Getroot(R,x);
        fa[rt]=x;near[rt]=R;
        erz[x].push_back(rt);
        solve(rt,x);
    }
}
void Update(ll x,ll e)
{
    ll st=x;d[x]+=e;
    while(x)
    {
        ll dis=sp::Dis(st,fa[x]);
        d[fa[x]]+=e;//加上兵队总数
        val[fa[x]]+=e*dis;//加上到达父亲的代价
        tofa[x]+=e*dis;//加上对父亲的贡献
        x=fa[x];
    }
}
ll Calc(ll x)//询问以x为补给站时的答案
{
    ll res=val[x],st=x;//初值为儿子到x的答案
    while(x)//暴跳点分树父亲
    {
        ll dis=sp::Dis(st,fa[x]);
        res+=(d[fa[x]]-d[x])*dis;//其他兄弟会多走一段路
        res+=val[fa[x]]-tofa[x];//加上其他兄弟对答案的贡献
        x=fa[x];
    }
    return res;
}
ll Query(ll x)
{
    ll tt=Calc(x);
    for(ll i=0,l=erz[x].size();i<l;i++)
        if(Calc(near[erz[x][i]])<tt) return Query(erz[x][i]);
    return tt;
}
int main()
{
    n=read();q=read();
    for(ll i=2;i<=n;i++)
    {
        ll x=read(),y=read(),w=read();
        link(x,y,w);
    }
    sp::dfs1(1);sp::dfs2(1);
    rt=0;sum=mx[0]=n;
    Getroot(1,0);
    Root=rt;
    solve(rt,0);
    for(ll i=1;i<=q;i++)
    {
        ll x=read(),w=read();
        Update(x,w);
        printf("%lld\n",Query(Root));
    }
    return 0;
}

写起来真的要比捉迷藏简单多了诶

你来看看咯 https://www.cnblogs.com/xzyxzy/p/9481496.html

欢迎给博主提供毒瘤题