[DS记录]P3345 [ZJOI2015]幻想乡战略游戏

· · 个人记录

题意: 给出一棵树,有边权点权,支持单点修改,查询重心到各个点的加权距离和。

度数不超过k=20 ,n,q\leq 10^5 ,时限\texttt{6s}.

曾经仰望这题2年。

解法1 : 动态点分治

这是“按重心移动”和“动态点分治”的结合。

先找重心,再求加权距离和。

忽略边权,一个充要条件是 : 带权重心的每个子树中的点权和,不超过总点权的一半。

使用全局dfs序树状数组维护子树点权和,由于度数小,在点分树上依次枚举转移方向即可。

注意,我们修改的时候只会影响到O(\log n)个点分树点,我们可以顺便查询子树并保存最优的转移方向,避免每次询问都要用树状数组。可以平衡一下复杂度。

这部分的时间是O(q(\log^2n+k\log n)).

考虑求答案,从点分树向上跳,每次查询不在来时子树的加权距离和,这直接拿个变量记一下就好。

空间复杂度O(n\log n),时间复杂度O(n\log n+q(\log^2n+k\log n))。

性质不如下一个解法优美,代码就先咕了。

解法2 : 线段树+树剖

考虑不跳重心,而是从根一步步向下爬。

观察我们的决策条件,发现若子树大小不足总点权一半则向上爬,这个点不可能是答案。

反之,答案一定在其子树中(因为不能向上回去了)。若某个点本身满足这个条件,而子树内又无这类点,它就是答案。

其实可以发现,这类点分布成一条从根直下的简单路径,这是个非常强的性质。我们要找的就是深度最大的这类点。

考虑答案对子树大小的影响,不难发现就是链修改,可以树剖维护。

现在我们需要找点权大于S/2的点的最大深度,而且要在原线段树上找,不能变换下标,看起来有点棘手。

事实上,从根直下的简单路径性质很好。重链的下标排布正是按照dfs的访问顺序,子树内,深度大的重链排在后面。可以直接线段树上二分,尽量往右走就是了。

接下来考虑如何求答案 : \sum\limits_{v}dis(u,v)*w[v]

可以拆成 \sum\limits_{v}\big(dep[u]+dep[v]-2*dep[lca(u,v)]\big)*w[v]

前两个容易维护,关键是\sum\limits_{v}dep[lca(u,v)]*w[v]咋搞。

不难转化为树上到根的公共路径,这也可以链修改以及链查询维护。

具体地讲,点有两个点权(a,b),其中b为父边长度,每次对a区间加,维护a*b的和。可以记录区间内b的和即可传递加法标记。

复杂度O(n+q\log^2n),不需要度数的性质,代码也非常好写。

#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 200500
using namespace std;
inline int read(){
  int X=0;char ch=0,w=0;
  while(ch<48||ch>57)ch=getchar(),w|=(ch=='-');
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return w?-X:X;
}
vector<int> g[MaxN],l[MaxN];
inline void adl(int f,int t,int len){
  g[f].pb(t);l[f].pb(len);
  g[t].pb(f);l[t].pb(len);
}
struct TNode
{int tf,f,son,siz,dep,lf;}b[MaxN];
int dis[MaxN];
void dfs1(int u)
{
  b[u].siz=1;
  b[u].dep=b[b[u].f].dep+1;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=b[u].f){
      dis[v]=dis[u]+(b[v].lf=l[b[v].f=u][i]);
      dfs1(v);
      b[u].siz+=b[v].siz;
      if (b[v].siz>b[b[u].son].siz)
        b[u].son=v;
    }
}
int tim,tp[MaxN],id[MaxN];
void dfs2(int u,int top)
{
  tp[id[u]=++tim]=u;
  b[u].tf=top;
  if (!b[u].son)return ;
  dfs2(b[u].son,top);
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=b[u].f&&v!=b[u].son)
      dfs2(v,v);
}
struct SGT_Node{
  ll x;int m,tag,d;
  inline void ladd(int t){
    x+=1ll*d*t;
    m+=t;tag+=t;
  }
}a[MaxN<<2];
void build(int l,int r,int u)
{
  if (l==r){
    a[u].d=b[tp[l]].lf;
    return ;
  }int mid=(l+r)>>1;
  build(l,mid,u<<1);
  build(mid+1,r,u<<1|1);
  a[u].d=a[u<<1].d+a[u<<1|1].d;
}
inline void up(int u){
  a[u].x=a[u<<1].x+a[u<<1|1].x;
  a[u].m=max(a[u<<1].m,a[u<<1|1].m);
}
inline void ladd(int u){
  if (!a[u].tag)return ;
  a[u<<1].ladd(a[u].tag);
  a[u<<1|1].ladd(a[u].tag);
  a[u].tag=0;
}
int wfc,wfl,wfr;
void add(int l,int r,int u)
{
  if (wfl<=l&&r<=wfr){
    a[u].ladd(wfc);
    return ;
  }ladd(u);
  int mid=(l+r)>>1;
  if (wfl<=mid)add(l,mid,u<<1);
  if (wfr>mid)add(mid+1,r,u<<1|1);
  up(u);
}
ll sum;
void qry(int l,int r,int u)
{
  if (wfl<=l&&r<=wfr)
    {sum+=a[u].x;return ;}
  int mid=(l+r)>>1;ladd(u);
  if (wfl<=mid)qry(l,mid,u<<1);
  if (wfr>mid)qry(mid+1,r,u<<1|1);
}
int T,n;
int find(int l=1,int r=n,int u=1)
{
  if (l==r)return tp[l];
  int mid=(l+r)>>1;ladd(u);
  if ((a[u<<1|1].m<<1)>T)
    return find(mid+1,r,u<<1|1);
  return find(l,mid,u<<1);
}
void pathop(int x,void (*op)(int,int,int)){
  while(x){
    wfl=id[b[x].tf];wfr=id[x];
    op(1,n,1);x=b[b[x].tf].f;
  }
}
int m;ll S;
int main()
{
  n=read();m=read();
  for (int i=1,f,t;i<n;i++)
    {f=read();t=read();adl(f,t,read());}
  dfs1(1);dfs2(1,1);build(1,n,1);
  for (int i=1,u;i<=m;i++){
    u=read();T+=(wfc=read());
    S+=1ll*dis[u]*wfc;
    pathop(u,add);
    u=find();
    ll ans=S+1ll*T*dis[u];
    sum=0;pathop(u,qry);
    printf("%lld\n",ans-2*sum);
  }return 0;
}