「ZJOI2015」幻想乡战略游戏
题目描述
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构，一共有n块空地，这些空地被n-1条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。 如果补给站在点u上，并且空地v上有dv个单位的军队，那么幽香每天就要花费dv*dist(u,v)的金钱来补给这些军队。
由于幽香需要补给所有的军队，因此幽香总共就要花费为Sigma(Dv*dist(u，v),其中1<=V<=N)的代价。其中dist(u,v)表示u个v在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。
但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。
输入输出格式
输入格式：
第一行两个数n和Q分别表示树的点数和幽香操作的个数，其中点从1到n标号。 接下来n-1行，每行三个正整数a,b,c，表示a和b之间有一条边权为c的边。 接下来Q行，每行两个数u,e，表示幽香在点u上放了e单位个军队（如果e<0，就相当于是幽香在u上减少了|e|单位个军队，说白了就是du←du+e）。数据保证任何时刻每个点上的军队数量都是非负的。
输出格式：
对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。
输入输出样例
说明
对于所有数据，1<=c<=1000, 0<=|e|<=1000, n<=10^5, Q<=10^5
非常神奇的是，对于所有数据，这棵树上的点的度数都不超过20，且N，Q>=1
分析
考虑答案的形式，发现跟带权重心非常类似。
假设当前补给站为\(u\)，并强制以\(u\)为根，\(v\)为\(u\)的一个子节点，\(sumd_u\)和\(sumd_v\)分别为\(u\)的子树内的\(d\)之和以及\(v\)的子树内的\(d\)之和，\(len(u,v)\)为边\((u,v)\)的长度。
如果将补给站迁移到点\(v\)，那么\(v\)的子树内的点到补给站的距离减少了\(len(u,v)\)，其他的点到补给站的距离增加了\(len(u,v)\)。也就是说，补给站迁移到点\(v\)时，代价的增量为：
\]
整理一下，得出性质：\(u\)为根，\(v\)为\(u\)的子节点，补给站在\(v\)比\(u\)优，当且仅当：
\]
显然满足条件的\(v\)最多只有一个。这时候，如果没有满足条件的\(v\)，则\(u\)为最优位置。否则最优位置在\(v\)的子树内。
一个一个跳肯定不行，所以考虑使用点分树加速跳跃过程。具体而言，如果发现\(u\rightarrow v\)更优的话，那么就递归计算\(v\)子树中的重心，即\(u\)在点分树上的儿子节点。运用换根DP的知识我们可以维护点分树上面每个节点子树的答案并且做到\(O(\log n)\)查询每个节点换根后的答案。
时间复杂度\(O(n\log n+Q\log^2 n)\)
动态点分治的作用：在点分治的过程中，一般我们面对的问题都是静态的。如果涉及到修改这类的操作，我们就希望找到我们是如何处理到当前的修改点的，换而言之，我们希望记录下点分治的过程，这样可以通过爬点分树等操作消除影响。
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
co int N=2e5+1;
int n,m;
namespace T{ // original tree
vector<pii> e[N];
int lg[N*2],st[N*2][18],dis[N],pos[N],dfn;
void dfs(int u,int fa){
st[pos[u]=++dfn][0]=dis[u];
for(int i=0,v;i<e[u].size();++i){
if((v=e[u][i].first)==fa) continue;
dis[v]=dis[u]+e[u][i].second,dfs(v,u);
st[++dfn][0]=dis[u];
}
}
void init(){
lg[0]=-1;
for(int i=1;i<=n<<1;++i) lg[i]=lg[i>>1]+1;
dfs(1,0),assert(dfn==2*n-1);
for(int j=1;1<<j<=dfn;++j)
for(int i=1;i+(1<<j)-1<=dfn;++i)
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
int get_dis(int u,int v){
if(pos[u]>pos[v]) swap(u,v);
int k=lg[pos[v]-pos[u]+1];
return dis[u]+dis[v]-2*min(st[pos[u]][k],st[pos[v]-(1<<k)+1][k]);
}
}
int vis[N],sum,root,siz[N],f[N],par[N];
ll down[N],up[N],sumd[N];
vector<pii> g[N];
void get_root(int u,int fa){
siz[u]=1,f[u]=0;
for(int i=0,v;i<T::e[u].size();++i){
if(vis[v=T::e[u][i].first]||v==fa) continue;
get_root(v,u);
siz[u]+=siz[v],f[u]=max(f[u],siz[v]);
}
f[u]=max(f[u],sum-siz[u]);
if(f[u]<f[root]) root=u;
}
void work(int u,int fa){
vis[u]=1,par[u]=fa;
for(int i=0,v;i<T::e[u].size();++i){
if(vis[v=T::e[u][i].first]) continue;
sum=siz[v],root=0,get_root(v,0);
g[u].push_back(pii(root,v));
work(root,u);
}
}
void ins(int u,int val){
sumd[u]+=val;
for(int i=u;par[i];i=par[i]){
int dist=T::get_dis(par[i],u);
down[par[i]]+=(ll)dist*val; // underneath ans
up[i]+=(ll)dist*val; // upward transfer
sumd[par[i]]+=val;
}
}
ll calc(int u){
ll ans=down[u];
for(int i=u;par[i];i=par[i]){
int dist=T::get_dis(par[i],u);
ans+=down[par[i]]-up[i]+dist*(sumd[par[i]]-sumd[i]);
}
return ans;
}
ll query(int u){
ll ans=calc(u);
for(int i=0;i<g[u].size();++i)
if(calc(g[u][i].second)<ans)
return query(g[u][i].first);
return ans;
}
int main(){
// freopen("LG3345.in","r",stdin);
read(n),read(m);
for(int i=1,u,v,w;i<n;++i){
read(u),read(v),read(w);
T::e[u].push_back(pii(v,w)),T::e[v].push_back(pii(u,w));
}
T::init();
sum=n,f[0]=n,get_root(1,0);
int tmp=root;work(root,0),root=tmp;
for(int u,e;m--;){
read(u),read(e),ins(u,e);
printf("%lld\n",query(root));
}
return 0;
}