bzoj 3924 [Zjoi2015]幻想乡战略游戏——动态点分治（暴力移动找重心）

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3924

度数只有20，所以从一个点暴力枚举其出边，就能知道往哪个方向走。

知道方向之后直接走到点分树的那个部分的儿子上，即一下走到了那个方向的重心。这样只会走 log 次。

需要通过点分树上维护的信息实现 log 查询一个点作为根的答案。

可以维护 f [ i ] 表示自己作为重心管辖部分的点 j 的 \( \sum dis( i , j ) * w[ j ] \)， g [ i ] 表示自己管辖的点 j 的 \( \sum dis( pre[ i ] , j ) * w[ j ] \) ，再维护自己管辖的点的 \( \sum w[ j ] \) ，就能查询答案了。每次就是枚举自己点分树上的父亲，用它们的 f 减去它们下一层孩子的 g 加到自己的答案里，再用它们的 w 减去他们下一层孩子的 w 再乘上到自己的距离加到自己的答案里。

不知为什么时限是 100 s ，所以这样就能过了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e5+,K=;

int n,hd[N],xnt,to[N<<],nxt[N<<],ew[N<<],eto[N<<];

int dep[N],pre[N][K],dis[N][K],siz[N],mn,rt; bool vis[N];

ll f[N],g[N],w[N];int xt,go[N],nt[N],hed[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

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

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

void add(int x,int y,int z){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;ew[xnt]=z;}

void addx(int x,int y){go[++xt]=y;nt[xt]=hed[x];hed[x]=xt;}

void getrt(int cr,int fa,int s)

{

  siz[cr]=;int mx=;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)

      {

    getrt(v,cr,s);siz[cr]+=siz[v];mx=Mx(mx,siz[v]);

      }

  mx=Mx(mx,s-siz[cr]); if(mx<mn)mn=mx,rt=cr;

}

void dfs(int cr,int fa,int ds)

{

  pre[cr][++dep[cr]]=rt;dis[cr][dep[cr]]=ds;

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]]&&v!=fa)dfs(v,cr,ds+ew[i]);

}

void init(int cr,int s)

{

  vis[cr]=;dfs(cr,,);

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])

      {

    int ts=(siz[v]<siz[cr]?siz[v]:s-siz[cr]);

    mn=N;getrt(v,cr,ts);addx(cr,rt);

    eto[i]=rt;init(rt,ts);

      }

}

void mdfy(int cr,int k)

{

  for(int i=dep[cr],v;i;i--)

    {

      w[v=pre[cr][i]]+=k;

      f[v]+=(ll)dis[cr][i]*k;

      g[v]+=(ll)dis[cr][i-]*k;

    }

}

ll calc(int cr)

{

  ll ret=f[cr];

  for(int i=dep[cr]-,x,y;i;i--)

    ret+=f[x=pre[cr][i]]-g[y=pre[cr][i+]]+(w[x]-w[y])*dis[cr][i];

  return ret;

}

void solve(int cr,ll nw)

{

  ll mn=nw;int bh=;

  for(int i=hd[cr];i;i=nxt[i])

    {

      ll tmp=calc(to[i]);

      if(tmp<nw&&tmp<mn)mn=tmp,bh=i;

    }

  if(!bh){printf("%lld\n",nw);return;}

  solve(eto[bh],calc(eto[bh]));

}

int main()

{

  n=rdn();int Q=rdn();

  for(int i=,u,v,k;i<n;i++)

    u=rdn(),v=rdn(),k=rdn(),add(u,v,k),add(v,u,k);

  mn=N;getrt(,,n);int cr=rt;init(rt,n);

  int x,k;

  while(Q--)

    {

      x=rdn();k=rdn();mdfy(x,k);

      solve(cr,f[cr]);

    }

  return ;

}

巴特西

bzoj 3924 [Zjoi2015]幻想乡战略游戏——动态点分治（暴力移动找重心）

最新文章

热门文章