zjoi2015 幻想乡战略游戏

这里提供一个复杂度比较对的树剖做法。

这个题分为两步。

首先我们要找到那个使得 \(\sum\limits_{i=1}dist(u,i)d_i\) 最小的 \(u\) 。

其实这个点是有定义的。

考虑我们怎么定义重心的（或者说重心的性质）。

有重心 \(u\) 为使得 \(\sum\limits_{i=1}dist(u,i)\) 最小的 \(u\)。

那么本题所定义的可以理解成带权重心。

考虑如何求带权重心。

首先随便定一个根，把这棵树转化成有根树。其中整个树的权值和为 \(all\) ,点 \(x\) 的子树权值和为 \(sum_x\)。

那么如果当前在点 \(x\) ，如果 \(x\) 的某一个儿子 \(y\) 更满足使 \(\sum dist(y,i)d_i\) 的条件，那么必须满足 \((all-sum_y)\cdot w<sum_y\cdot w\) ,也就是 \(sum_y>\frac{all}{2}\) 。

那么把 \(x\) 的重心转到 \(y\) 一定更优，由于此时 \(sum_y>\frac{all}{2}\) 所以只可能有一个儿子满足转移条件。

如果 \(x\) 的儿子只存在等于或者不存在 \(sum_y>\frac{all}{2}\)，那么 \(x\) 遍为重心。

所以现在只需要维护子树权值和，找到最深的满足 \(sum_y>\frac{all}{2}\) 的 \(y\) 便为所求位置。

这个可以通过用 \(dfs\) 序列建出线段树，在线段树上 找到一个最靠后，满足 \(sum_y>\frac{all}{2}\) 的 \(y\),在线段树上二分即可。

由于一条链的 \(dfs\) 序严格单调增，所以可以二分。

那么现在要求解答案。(\(f_i\) 表示 \(u\) 的第 \(i\) 级祖先,\(sum_j\) 表示以 \(j\) 为根的子树权值和。)。 \[ \begin{aligned} \sum_{i} dist(u,i)&=\sum_i dep(u)+dep(i)-2\cdot dep(lca(u,i))\\ &=dep(u) \sum_i 1+\sum_i dep(i)+\sum_i dep(lca(u,i))\\ \sum_i dep(lca(u,i))&=\sum_{j=1}dep_{f_i} (sum_{f_{j}}-sum_{f_{j-1}})\\ &=\sum_{j=1}dep_{f_i}\cdot sum_{f_j}-\sum_{j=0}dep_{f_{j+1}}sum_j=\sum_{j=1}(dep_{f_{j}}-{dep_{f_{j+1}}})sum_j\\ &=\sum_{j=1} w_jsum_j \end{aligned} \] 怎么维护？

链剖维护的充要条件是维护的信息可以合并，线段树区间修改的充要条件是可以 \(O(1)\) pushdown，同时可以合并。

设 \(v_j=w_jsum_j\) ,我们现在要维护 \(v_j\) 的区间和，同时要能对 \(sum_j\) 区间修改。

考虑一段区间怎么快速更新和，显然有 \(\sum_{j=l}^{r}w_j(sum_j+v)=\sum_{j=l}^rw_jsum_j+v\cdot sum_{j=l}^rw_j\)。

发现只需要维护区间的 \(w_j\) 的和，便能更新区间的 \(v_j\) 的和，而 \(w_j\) 的值不变，是 \(j\) 的一个属性所以很好维护。

那么这道题就做完了。时间复杂度 \(\mathcal{O(n\log n\log n)}\) 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
vector<pair<int,int> >v[N];int fa[N],w[N];
int n,q;
inline void read(int &x)
{
    char c=getchar();x=0;bool f=0;
    while(c>'9'||c<'0') {if(c=='-') f=1;c=getchar();}
    while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    if(f) x=-x;
}
int sz[N],dfn[N],hson[N],dep[N],dis[N];
inline void dfs(int x,int f)
{
    fa[x]=f;sz[x]=1;int mx=0;dep[x]=dep[f]+1;
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i].first,z=v[x][i].second;
        if(y==f) continue;dis[y]=dis[x]+z;
        w[y]=z;dfs(y,x);sz[x]+=sz[y];
        if(sz[y]>mx) mx=sz[y],hson[x]=y;
    }
}
int top[N],cnt,num[N];
inline void redfs(int x,int f,int tp)
{
    dfn[x]=++cnt;num[cnt]=x;top[x]=tp;
    if(hson[x]) redfs(hson[x],x,tp);
    for(int i=0;i<v[x].size();i++)
    {
        int y=v[x][i].first;
        if(y==f||y==hson[x]) continue;
        redfs(y,x,y);
    }
}

struct seg{
    int l,r,tag,mx,v,sumv;
}t[N<<2];
inline void build(int pos,int l,int r)
{
    t[pos].l=l,t[pos].r=r;
    if(l==r) 
    {
        t[pos].v=w[num[l]];
        return ;
    }
    int mid=l+r>>1;
    build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);
    t[pos].v=t[pos<<1].v+t[pos<<1|1].v;
}
inline void pushdown(int pos)
{
    if(t[pos].tag==0) return ;
    int tag=t[pos].tag;t[pos].tag=0;
    t[pos<<1].tag+=tag,t[pos<<1].mx+=tag;
    t[pos<<1|1].tag+=tag,t[pos<<1|1].mx+=tag;
    t[pos<<1].sumv+=tag*t[pos<<1].v;
    t[pos<<1|1].sumv+=tag*t[pos<<1|1].v;
}
inline void modify(int pos,int x,int y,int v)
{
    if(x<=t[pos].l&&t[pos].r<=y)
    {
        t[pos].sumv+=v*t[pos].v;
        t[pos].tag+=v;t[pos].mx+=v;return ;
    }
    pushdown(pos);
    int mid=t[pos].l+t[pos].r>>1;
    if(y<=mid) modify(pos<<1,x,y,v);
    else if(x>mid) modify(pos<<1|1,x,y,v);
    else modify(pos<<1,x,y,v),modify(pos<<1|1,x,y,v);
    t[pos].mx=max(t[pos<<1].mx,t[pos<<1|1].mx);
    t[pos].sumv=t[pos<<1].sumv+t[pos<<1|1].sumv;
}
inline int query(int pos,int v)
{
    if(t[pos].l==t[pos].r) return t[pos].l;
    pushdown(pos);
    if(2*t[pos<<1|1].mx>v) return query(pos<<1|1,v);
    return query(pos<<1,v);
}
inline int ask(int pos,int x,int y)
{
    if(x<=t[pos].l&&t[pos].r<=y) return t[pos].sumv;
    pushdown(pos);
    int mid=t[pos].l+t[pos].r>>1;
    if(y<=mid) return ask(pos<<1,x,y);
    else if(x>mid) return ask(pos<<1|1,x,y);
    return ask(pos<<1,x,y)+ask(pos<<1|1,x,y);
}
int val[N];
int v1,v2;
signed main()
{
    //freopen("1.in","r",stdin);
    //freopen("res","w",stdout);
    read(n),read(q);
    for(int i=1;i<n;i++)
    {
        int x,y,z;read(x),read(y);read(z);
        v[x].push_back(make_pair(y,z));v[y].push_back(make_pair(x,z));
    }
    dfs(1,0);redfs(1,0,1);
    int all=0;
    build(1,1,n);
    while(q--)
    {
        int x,y;read(x),read(y);all+=y;val[x]+=y;v1+=y;v2+=y*(dis[x]);
        while(x!=0)
        {
            modify(1,dfn[top[x]],dfn[x],y);
            x=fa[top[x]];
        }
        int pos=num[query(1,all)],ans=0;
        x=pos;
        while(x!=0)
        {
            ans+=ask(1,dfn[top[x]],dfn[x]);
            x=fa[top[x]];
        }
        ans=v2+dis[pos]*v1-2*ans;
        printf("%lld\n",ans);
    }
}