题解 P3345 【[ZJOI2015]幻想乡战略游戏】

很久没有被题目恶心得欲仙欲死了 于是今天找了个虐 ## 正文 整理好思路其实这题是要比捉迷藏、Qtree4好写的 ### Step1 建好点分树以及打好树剖（用来求两点距离） ### Step2 维护三个东西就很好计算以指定的某个点为补给站的答案了 ``` d[x]表示点分树上以x为根的子树的兵队总数 val[x]表示点分树上以x为根的子树的兵队到达x的代价和 tofa[x]表示点分树上以x为根的子树的兵队到达x的父亲的代价和 ``` 于是具体操作在Calc函数中，有详细解释 ### Step3 具体代码流程 1.建好点分树 2.修改某个点，暴跳点分树的父亲对应修改三个值 3.从点分树根开始查询，找到真正的带权重心后返回答案（Query函数有详细注释） ### 注意事项 1.要开long long （反正有6秒你开gedit就可以把int全部换成long long） 2.贪心跳带权重心，你此时在x点，点分树上x的儿子有y，你看x要不要跳到y，需要检查的是y的分治区域与x直接相连的那个点（near[y]）的答案是否比x的小，而不是检查y的 3.本人太菜在Getroot没有判断vis而TLE了一次 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<vector> #define ll long long using namespace std; ll read() { char ch=getchar();ll h=0,t=1; while((ch>'9'||ch<'0')&&ch!='-') ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar(); return h*t; } const ll N=100100; struct edge{ll next,to,w;}a[N<<1]; ll n,q,head[N],cnt,rt,mx[N],siz[N],fa[N],vis[N],sum; ll d[N],val[N],tofa[N],Root,near[N]; vector<int> erz[N]; /* d[x]表示点分树上以x为根的子树的兵队总数 val[x]表示点分树上以x为根的子树的兵队到达x的代价和 tofa[x]表示点分树上以x为根的子树的兵队到达x的父亲的代价和 erz[x]记录点分树上x的儿子 near[x]表示x的分治区域与x点分树父亲的相邻结点 */ void Max(ll &a,ll b) {if(b>a) a=b;} void link(ll x,ll y,ll w) { a[++cnt]=(edge){head[x],y,w};head[x]=cnt; a[++cnt]=(edge){head[y],x,w};head[y]=cnt; } namespace sp { ll siz[N],dep[N],son[N],top[N],tot,dfn[N],fa[N]; void dfs1(ll x) { for(ll i=head[x];i;i=a[i].next) { ll R=a[i].to;if(R==fa[x]) continue; fa[R]=x;siz[R]=1;dep[R]=dep[x]+a[i].w; dfs1(R);siz[x]+=siz[R]; if(siz[R]>siz[son[x]]) son[x]=R; } } void dfs2(ll x) { top[x]=x;dfn[x]=++tot; if(son[fa[x]]==x) top[x]=top[fa[x]]; if(son[x]) dfs2(son[x]); for(ll i=head[x];i;i=a[i].next) if(a[i].to!=son[x]&&a[i].to!=fa[x]) dfs2(a[i].to); } ll LCA(ll x,ll y) { while(top[x]^top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } ll Dis(ll x,ll y) {return dep[x]+dep[y]-2*dep[LCA(x,y)];} } void Getroot(ll x,ll f) { siz[x]=1;mx[x]=0; for(ll i=head[x];i;i=a[i].next) { ll R=a[i].to;if(R==f||vis[R]) continue; Getroot(R,x);siz[x]+=siz[R]; Max(mx[x],siz[R]); } Max(mx[x],sum-siz[x]); if(mx[x]<mx[rt]) rt=x; } void solve(ll x,ll f) { vis[x]=1; for(ll i=head[x],tt=sum;i;i=a[i].next) { ll R=a[i].to;if(vis[R]) continue; rt=0;sum=siz[R]>siz[x]?tt-siz[x]:siz[R]; Getroot(R,x); fa[rt]=x;near[rt]=R; erz[x].push_back(rt); solve(rt,x); } } void Update(ll x,ll e) { ll st=x;d[x]+=e; while(x) { ll dis=sp::Dis(st,fa[x]); d[fa[x]]+=e;//加上兵队总数 val[fa[x]]+=e*dis;//加上到达父亲的代价 tofa[x]+=e*dis;//加上对父亲的贡献 x=fa[x]; } } ll Calc(ll x)//询问以x为补给站时的答案 { ll res=val[x],st=x;//初值为儿子到x的答案 while(x)//暴跳点分树父亲 { ll dis=sp::Dis(st,fa[x]); res+=(d[fa[x]]-d[x])*dis;//其他兄弟会多走一段路 res+=val[fa[x]]-tofa[x];//加上其他兄弟对答案的贡献 x=fa[x]; } return res; } ll Query(ll x) { ll tt=Calc(x); for(ll i=0,l=erz[x].size();i<l;i++) if(Calc(near[erz[x][i]])<tt) return Query(erz[x][i]); return tt; } int main() { n=read();q=read(); for(ll i=2;i<=n;i++) { ll x=read(),y=read(),w=read(); link(x,y,w); } sp::dfs1(1);sp::dfs2(1); rt=0;sum=mx[0]=n; Getroot(1,0); Root=rt; solve(rt,0); for(ll i=1;i<=q;i++) { ll x=read(),w=read(); Update(x,w); printf("%lld\n",Query(Root)); } return 0; } ``` 写起来真的要比捉迷藏简单多了诶 你来看看咯 https://www.cnblogs.com/xzyxzy/p/9481496.html ~~欢迎给博主提供毒瘤题~~