題目大意：
有邊權點權的樹，動態修改點權
每次修改后求帶權重心x (\(minimize\) \(S=\sum_i val[i]*dist[x][i]\))
分析：
從暴力找突破口：
對于邊x,y，設長度為len，切斷后x半邊樹權值和為\(w_1\)，y半邊樹為\(w_2\)
若從重心從x轉到到y,則\(S+w_1*len-w_2*len\)
y比x優當且僅當\(w_2>w_1\)
設當前根為root，若root的一兒子x，滿足\(w_x>w_{root}-w_x\)，則x更優，且可以證明\(w_x>\frac {w_{root}} 2\),即不會存在第二個兒子y也比root優
做法：
暴力做法深度無保證，但\(w_x>w_{root}-w_x\)可以確定答案在x子樹
我們用點分治樹保證深度
新的問題：點分治樹怎么求w
對于邊x,y,設x半邊樹中所有點到x距離為\(d_1\),y半邊樹中所有點到y距離為\(d_2\)
所有點到x距離為\(d_1+d_2+w_2*len\)
所有點到y距離為\(d_1+d_2+w_1*len\)
可以了啊，這就是動態點分治模板了
詢問復雜度\(nlog^2n\)
==============================================================================================
后來信息隊一位善于創新的大神想到了nlogn的方法
x為rt，y為點分兒子時
x在上則兩邊權值和分別為w(y)和w(root)-w(y)
y在上則兩邊權值和分別為w(root)-w(x)+w(y)和w(x)-w(y)
乍一看非常正確，用rmq求個lca就可以O(1)判上下，超簡便維護
但如果如圖 :
兜來兜去的圖發現bug多多
吸取經驗
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long LL;
const int M=100007;
const int N=M*20*2;
inline int rd(){int x=0;bool f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=0;for(;isdigit(c);c=getchar())x=x*10+c-48;return f?x:-x;
}int n,m;int g[M],te;
struct edge{int y,next;LL d;
}e[M<<1];
void addedge(int x,int y,LL d){e[++te].y=y;e[te].d=d;e[te].next=g[x];g[x]=te;
}int fir[M],td;
struct down{int y;//點分兒子int son;//親兒子int next;
}dw[M];
void adddw(int x,int y,int son){dw[++td].y=y;dw[td].son=son;dw[td].next=fir[x];fir[x]=td;
}int hd[M],tu;
struct uppp{int all,sub,next;LL dis;
}up[N];
void addup(int x,int all,int sub,LL dis){up[++tu].all=all;up[tu].sub=sub;up[tu].dis=dis;up[tu].next=hd[x];hd[x]=tu;
}struct node{LL sum,val;
}a[M<<1];
int idrt,idsub,nw;int sz[M],vis[M];
int mi,size,rt,root;void getsz(int x,int fa){sz[x]=1;int p,y;for(p=g[x];p;p=e[p].next)if(!vis[y=e[p].y]&&y!=fa){getsz(y,x);sz[x]+=sz[y];}
}void getrt(int x,int fa){int f,p,y;f=size-sz[x];for(p=g[x];p;p=e[p].next)if(!vis[y=e[p].y]&&y!=fa){getrt(y,x);f=max(f,sz[y]);}if(f<mi) mi=f,rt=x;
}void dfs(int x,int fa,LL dis){addup(x,idrt,idsub,dis);int p,y;for(p=g[x];p;p=e[p].next)if(!vis[y=e[p].y]&&y!=fa){dfs(y,x,dis+e[p].d);}
}void work(int frm,int drt){getsz(frm,0);mi=size=sz[frm];getrt(frm,0);int x=rt,p,y;vis[x]=1;idrt=++nw;addup(x,idrt,-1,0);if(drt) adddw(drt,x,frm);else root=x;for(p=g[x];p;p=e[p].next)if(!vis[y=e[p].y]){idsub=++nw;dfs(y,x,e[p].d);}for(p=g[x];p;p=e[p].next)if(!vis[y=e[p].y]) work(y,x);
}void update(int x,LL y){int p;for(p=hd[x];p;p=up[p].next){a[up[p].all].val+=y;a[up[p].all].sum+=y*up[p].dis;if(up[p].sub!=-1){a[up[p].sub].val+=y;a[up[p].sub].sum+=y*up[p].dis;}}
}LL get(int x){LL res=0;int p;for(p=hd[x];p;p=up[p].next){res+=a[up[p].all].sum;res+=a[up[p].all].val*up[p].dis;if(up[p].sub!=-1){res-=a[up[p].sub].sum;res-=a[up[p].sub].val*up[p].dis;}}return res;
}int anst;
void find(int x){int p,y,bb=1;for(p=fir[x];p;p=dw[p].next)if(get(x)>=get(dw[p].son)){bb=0;find(dw[p].y);break;}if(bb) anst=x;
}int main(){int i,x,y,z;n=rd();m=rd();for(i=1;i<n;i++){x=rd(),y=rd(),z=rd();addedge(x,y,z);addedge(y,x,z);}work(1,0);for(i=1;i<=m;i++){x=rd(),y=rd();update(x,y);find(root);printf("%lld\n",get(anst));}return 0;
}
轉載于:https://www.cnblogs.com/acha/p/6283355.html
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的bzoj 3924 幻想乡战略游戏的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
