题解 P3345 【[ZJOI2015]幻想乡战略游戏】
xzyxzy
2018-08-15 15:05:00
很久没有被题目恶心得欲仙欲死了
于是今天找了个虐
## 正文
整理好思路其实这题是要比捉迷藏、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
~~欢迎给博主提供毒瘤题~~