首页 > 代码库 > Bzoj3924--Fjoi2015幻想乡战略游戏
Bzoj3924--Fjoi2015幻想乡战略游戏
构造点分树,记录每个点管辖子树的大小Vc,这个点管辖子树内所有点到这个点的费用和Cos和这个子树对上一级重心费用的贡献Scos
每次修改直接点分树上修改
查询一个点,如果该点最大子树的大小大于全图一半,就把这个点除了最大子树外的部分贴到那个子树里对应的点上再递归去查询那个子树
如果最大子树也小于全图一半,那么这个点就是当前图的重心,答案就是Cos
代码 :
#include<bits/stdc++.h> #define PA pair<int,int> #define INF 0x3f3f3f3f #define LL long long using namespace std; inline int _max(int a,int b) {return a>b?a:b;} #define MAXN 100005 int n,m; int head[MAXN],cnt; struct Edge{ int next,to,w; }e[MAXN<<1]; inline void insert(int a,int b,int c) { e[++cnt].next=head[a];head[a]=cnt;e[cnt].to=b;e[cnt].w=c; e[++cnt].next=head[b];head[b]=cnt;e[cnt].to=a;e[cnt].w=c; } bool vis[MAXN];int sz[MAXN],weight[2]; void FindW(int v,int all) { vis[v]=1;sz[v]=0;int mx=0; for(int i=head[v];i;i=e[i].next) { if(!vis[e[i].to]) { FindW(e[i].to,all); mx=_max(mx,sz[e[i].to]);sz[v]+=sz[e[i].to]; } } sz[v]++;mx=_max(mx,all-sz[v]); if(weight[0]>mx) weight[0]=mx,weight[1]=v; vis[v]=0; } int Anc[MAXN][26],Len[MAXN],To[MAXN],Tdis[MAXN];LL Dis[MAXN][26]; void Comp(int v,int anc,int d) { vis[v]=1;sz[v]=0; Anc[v][++Len[v]]=anc;Dis[v][Len[v]]=d; for(int i=head[v];i;i=e[i].next) { if(!vis[e[i].to]) { Comp(e[i].to,anc,d+e[i].w); sz[v]+=sz[e[i].to]; } } sz[v]++;vis[v]=0; } void Solve(int w) { vis[w]=1;if(sz[w]==1) return; for(int i=head[w];i;i=e[i].next) { if(!vis[e[i].to]) { weight[0]=INF;FindW(e[i].to,sz[e[i].to]); To[weight[1]]=e[i].to;Tdis[weight[1]]=e[i].w; Comp(weight[1],weight[1],0); Solve(weight[1]); } } } LL Vc[MAXN],Cos[MAXN],Scos[MAXN],All; inline void Modify(int x,int y) { All+=y; for(int i=Len[x];i;i--) { Vc[Anc[x][i]]+=y; Cos[Anc[x][i]]+=y*Dis[x][i]; Scos[Anc[x][i]]+=y*Dis[x][i-1]; } } void Change(int x,int sp,LL v,LL c,int fx) { for(int i=Len[x];i;i--) { if(Anc[x][i]==sp) return; Vc[Anc[x][i]]+=v; Cos[Anc[x][i]]+=v*(Dis[x][i]+fx)+c; Scos[Anc[x][i]]+=v*(Dis[x][i-1]+fx)+c; } } LL Query(int v,int d) { LL ans,go,s=0; for(int i=head[v];i;i=e[i].next) if(Anc[e[i].to][d]&&Vc[Anc[e[i].to][d]]>s) s=Vc[Anc[e[i].to][d]],go=Anc[e[i].to][d]; if((s<<1)>All) { LL t=Vc[v]-Vc[go],c=Cos[v]-Scos[go]; Change(To[go],v,t,c,Tdis[go]); ans=Query(go,d+1); Change(To[go],v,-t,-c,Tdis[go]); return ans; } else return Cos[v]; } int main() { scanf("%d%d",&n,&m); for(int a,b,c,i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); insert(a,b,c); } weight[0]=INF;FindW(1,n); Comp(weight[1],weight[1],0); Solve(weight[1]); for(int x,y,i=1;i<=m;i++) { scanf("%d%d",&x,&y); Modify(x,y); printf("%lld\n",Query(Anc[1][1],2)); } return 0; }
Bzoj3924--Fjoi2015幻想乡战略游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。