P3345 [ZJOI2015]幻想乡战略游戏

题意：求带权重心，即求一个点 \(u\) ，使得最小化 \(\sum_{v}dis(u,v)\times w[v]\)，输出这个最小值。点权带修，多组询问。
动态点分治。。。
先建出点分树，以下的父子关系均是建立在点分树上的。
\(s[u]\) 表示子树 \(u\) 的点权和
\(sfa[u]\) 表示子树 \(u\) 对 \(fa[u]\) 的贡献，即 \(\sum_{v\in subtree(u)} dis(v,fa[u])\times w[v]\)
\(sdis[u]\) 表示 \(\sum_{v\in son(u)} sfa[v]\)
然后维护即可。

#include<iostream>
#include<cstdio>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
  register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
  do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010,Inf=0x3f3f3f3f;
int n,m,num,sum,rt,RT; bool vis[N];
int dfn[N],son[N],d[N],sz[N],mx[N],top[N],pre[N],fa[N];
ll s[N],sdis[N],sfa[N],dis[N];
struct G {
  int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],cnt;
  inline void add(int u,int v,int ww) 
    {vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;}
}e,pe;
inline void dfs(int u) { sz[u]=1;
  for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
    if(sz[v]) continue; pre[v]=u,d[v]=d[u]+1,dis[v]=dis[u]+e.w[i];
    dfs(v); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v;
  }
}
inline void dfs2(int u,int tp) {
  dfn[u]=++num,top[u]=tp;
  if(son[u]) dfs2(son[u],tp);
  for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
    if(dfn[v]) continue; dfs2(v,v);
  }
}
inline int lca(int u,int v) {
  while(top[u]!=top[v]) d[top[u]]>d[top[v]]?u=pre[top[u]]:v=pre[top[v]];
  return d[u]<d[v]?u:v;
}
inline ll dist(int u,int v) {return dis[u]+dis[v]-2*dis[lca(u,v)];}
inline void getrt(int u,int fa) {
  sz[u]=1,mx[u]=0;
  for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
    if(vis[v]||v==fa) continue;
    getrt(v,u); sz[u]+=sz[v];
    mx[u]=max(mx[u],sz[v]);
  } mx[u]=max(mx[u],sum-sz[u]);
  if(mx[u]<mx[rt]) rt=u;
}
inline void Pre(int u) {
  vis[u]=true;
  for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
    if(vis[v]) continue;
    sum=sz[v],rt=0; 
    getrt(v,u),getrt(rt,0);
    pe.add(fa[rt]=u,v,rt);
    Pre(rt);
  }
}
inline void change(int u,int vl) {
  s[u]+=vl;
  for(R i=u;fa[i];i=fa[i]) {
    R w=dist(u,fa[i]);
    s[fa[i]]+=vl;
    sdis[fa[i]]+=1ll*w*vl;
    sfa[i]+=1ll*vl*w;
  }
}
inline ll cal(int u) {
  register ll ret=sdis[u];
  for(R i=u;fa[i];i=fa[i]) {
    R w=dist(u,fa[i]);
    ret+=1ll*(s[fa[i]]-s[i])*w;
    ret+=sdis[fa[i]]-sfa[i];
  } return ret;
}
inline ll query(int u) {
  register ll ret=cal(u);
  for(R i=pe.fir[u];i;i=pe.nxt[i]) { R v=pe.vr[i];
    if(cal(v)<ret) return query(pe.w[i]);
  } return ret;
}
inline void main() {
  n=g(),m=g(); for(R i=1,u,v,w;i<n;++i) 
    u=g(),v=g(),w=g(),e.add(u,v,w),e.add(v,u,w);
  dfs(1),dfs2(1,1); sum=n,mx[rt]=Inf;
  getrt(1,-1),getrt(rt,-1),RT=rt,Pre(rt); 
  for(R i=1,u,c;i<=m;++i) 
    u=g(),c=g(),change(u,c),
    printf("%lld\n",query(RT));
}
} signed main() {Luitaryi::main(); return 0;}

线段树做法待补。

2019.12.17

P3345 [ZJOI2015]幻想乡战略游戏

原文：https://www.cnblogs.com/Jackpei/p/12057529.html