bzoj 4712: 洪水 — 树链剖分优化dp

 

4712: 洪水

Time Limit: 15 Sec  Memory Limit: 256 MB

Description

小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到
山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了：我们把这
个瀑布看成是一个n个节点的树，每个节点有权值（爬上去的代价）。小A要选择一些节点，以其权值和作为代价将
这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小A的朋友觉得这样
子太便宜小A了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小A觉得朋友做
得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全
无关）。于是他找到你。

Input

 输入文件第一行包含一个数n，表示树的大小。

接下来一行包含n个数，表示第i个点的权值。
接下来n-1行每行包含两个数fr，to。表示书中有一条边（fr，to）。
接下来一行一个整数，表示操作的个数。
接下来m行每行表示一个操作，若该行第一个数为Q，则表示询问操作，后面跟一个参数x，表示对应子树的根；若
为C，则表示修改操作，后面接两个参数x，to，表示将点x的权值加上to。
n<=200000，保证任意to都为非负数

Output

 对于每次询问操作，输出对应的答案，答案之间用换行隔开。

Sample Input

4
4 3 2 1
1 2
1 3
4 2
4
Q 1
Q 2
C 4 10
Q 1

Sample Output

3
1
4

HINT

Source

首先考虑没有修改，统计每个点的dp值，我们可以记 h[] 表示所以儿子的dp值和

所以更新很显然dp[x]=min(w[x],h[x])

继续考虑修改操作，考虑如何更新祖先

因为只有加操作，所以分几种情况（我们记更新后该点儿子的dp值增加了v，即该点的h[]值会增加v）

  1. 加之前，dp[x]=w[x]，所以加之后，该点的dp值不会变化，他祖先的dp值也同样不会被更新
  2. 加之前，dp[x]=h[x]，加之后，仍是h[x]，就是说明原先w[x]-h[x]>=v，我们就可以直接给他h[]值加上v
  3. 加之前，dp[x]=h[x]，加之后，变成w[x]，我们重新更新他的dp值，记录增加值，然后继续更新祖先

我们不难发现第3种情况最多有（n+m）次，因为只要被更新过，我们只能在更新他的w[]值之后才可能被更新

所以我们就可以使用树链剖分优化，线段树上维护区间（w[]-h[]）的最小值mn，我们对于两个情况3 的点中间直接区间修改

然后就是如何找到情况3的点，我们可以在每条重链的线段树中二分，找到第一个mn值小于v的点

需要注意的是线段树按dfs序存储，所以靠右的点更接近当前点，所以我们应该先在右侧寻找

然后，就一直循环，直到出现情况1或者到根节点

这样时间复杂度O(nlog²n)

 

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 200010
inline int rd()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int lj[N],fro[N<<1],to[N<<1],cnt;
void add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}
int n,T;
ll w[N];
int fa[N],son[N],sz[N],top[N],tid[N],tim,rk[N];
ll h[N],dp[N];
void dfs1(int x,int f)
{
	fa[x]=f;sz[x]=1;
	for(int i=lj[x];i;i=fro[i])
	{
		if(to[i]==f) continue;
		dfs1(to[i],x);
		h[x]+=dp[to[i]];sz[x]+=sz[to[i]];
		if(sz[son[x]]<sz[to[i]]) son[x]=to[i];
	}
	if(!son[x]) h[x]=inf;
	dp[x]=min(w[x],h[x]);
}
void dfs2(int x,int tp)
{
	tid[x]=++tim;
	rk[tim]=x;top[x]=tp;
	if(!son[x]) return;
	dfs2(son[x],tp);
	for(int i=lj[x];i;i=fro[i])
	{
		if(to[i]==son[x]||to[i]==fa[x]) continue;
		dfs2(to[i],to[i]);
	}
}
#define ls p<<1
#define rs p<<1|1
ll mn[N<<2],tg[N<<2];
void build(int p,int l,int r)
{
	if(l==r){mn[p]=w[rk[l]]-h[rk[l]];tg[p]=h[rk[l]];return;}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	mn[p]=min(mn[ls],mn[rs]);
}
inline void pd(int p)
{
	if(!tg[p]) return;
	mn[ls]-=tg[p];mn[rs]-=tg[p];
	tg[ls]+=tg[p];tg[rs]+=tg[p];
	tg[p]=0;
}
ll fd(int p,int l,int r,int x)
{
	if(l==r) return tg[p];
	pd(p);
	int mid=l+r>>1;
	return x<=mid?fd(ls,l,mid,x):fd(rs,mid+1,r,x);
}
ll ask(int x){return min(w[x],fd(1,1,n,tid[x]));}
void xg(int p,int l,int r,int x)
{
	if(l==r){mn[p]=w[rk[l]]-tg[p];return;}
	int mid=l+r>>1;
	if(x<=mid) xg(ls,l,mid,x);
	else xg(rs,mid+1,r,x);
	mn[p]=min(mn[ls],mn[rs]);
}
void xg(int p,int l,int r,int L,int R,ll v)
{
	if(l==L&&R==r){mn[p]-=v;tg[p]+=v;return;}
	pd(p);
	int mid=l+r>>1;
	if(R<=mid) xg(ls,l,mid,L,R,v);
	else if(L>mid) xg(rs,mid+1,r,L,R,v);
	else xg(ls,l,mid,L,mid,v),xg(rs,mid+1,r,mid+1,R,v);
	mn[p]=min(mn[ls],mn[rs]);
}
void chg(int x,int y,ll v)
{
	while(top[x]!=top[y]) xg(1,1,n,tid[top[x]],tid[x],v),x=fa[top[x]];
	xg(1,1,n,tid[y],tid[x],v);
}
int fd(int p,int l,int r,int L,int R,ll v)
{
	if(L<=l&&r<=R)
	{
		if(mn[p]>=v) return l;
		if(l==r) return 0;
	}
	pd(p);
	int mid=l+r>>1,tp;
	if(R<=mid) return fd(ls,l,mid,L,R,v);
	if(L>mid) return fd(rs,mid+1,r,L,R,v);
	tp=fd(rs,mid+1,r,L,R,v);
	if(!tp||tp>mid+1) return tp;
	tp=fd(ls,l,mid,L,R,v);
	return tp?tp:mid+1;
}
int gety(int x,ll v)
{
	int t=x,tp;x=fa[x];
	while(x)
	{
		tp=fd(1,1,n,tid[top[x]],tid[x],v);
		if(!tp) break;
		if(tp>tid[top[x]]) return rk[tp];
		t=top[x];x=fa[t]; 
	}
	return t;
}
void cg(int x,ll v)
{
	int tp=ask(x);
	ll d;
	w[x]+=v;
	xg(1,1,n,tid[x]);
	d=ask(x)-tp;
	if(!d) return;
	while(fa[x])
	{
		int y=gety(x,d);
		if(x!=y) chg(fa[x],y,d);
		x=fa[y];
		if(!x) return;
		tp=ask(x);
		chg(x,x,d);
		d=ask(x)-tp;
		if(!d) return;
	}
}
int main()
{
	n=rd();
	for(int i=1;i<=n;i++) w[i]=rd();
	int x,y;
	for(int i=1;i<n;i++)
	{
		x=rd();y=rd();
		add(x,y);add(y,x);
	}
	dfs1(1,0);dfs2(1,1);
	build(1,1,n);
	T=rd();
	char op[2];
	while(T--)
	{
		scanf("%s",op);x=rd();
		if(op[0]=='Q') printf("%lld\n",ask(x));
		else{y=rd();cg(x,y);}
	}
	return 0;
}

 

,

评论

还没有任何评论，你来说两句吧

发表评论

衫小寨 出品