蒟蒻刚学OI，求助大佬

WA 40 不知道为什么。

思路和题解有所不同，但都是DP。

考虑

f_u(x)

表示节点

u

子树中叶子深度改为

x

的最小代价。

是一个连续的下凸函数，且由斜率为整数的一次函数拼接而成。

考虑

f_u(x)

从

f_v

转移，这里

v

是

u

的儿子。

f_u(x)=\sum_v[\;\min_y(f_v(y)+|x-y-w_v|)\;]

，这里

w_v

表示

u

到

v

的导火索长度。

可以发现其中

\min_y(f_v(y)+|x-y-w_v|)

的部分关于自变量

x

是一个形如：

{f_v}'(x)=\left\{\begin{matrix}C+(L-x)&,&x<L\\C&,&L\le x\le R\\C+(x-R)&,&x>R\end{matrix}\right.

的函数。

其中

C,L,R

只与

f_v

中斜率为

0

的一段有关。

故对于任意的

f_u

，只需记录它的斜率为

0

的一段的端点和函数值即可。

也就是结构体 Dat 中的 x, y, z 三个变量。

在

f_u(x)=\sum_v{f_v}'(x)

中，需要将若干个形如上述的函数合并，并求出斜率为

0

的一段。请参见代码。

CPP

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
int N,M;
int h[600005],nxt[600005],to[600005],tot; LL w[600005];
void ins(int x,int y,LL z){nxt[++tot]=h[x];to[tot]=y;w[tot]=z;h[x]=tot;}
struct Dat{
	LL x,y,z;
	Dat(LL x=0,LL y=0,LL z=0):x(x),y(y),z(z){}
}f[600005],st[600005];
Dat operator+(Dat p1,LL p2){
	return Dat(p1.x+p2,p1.y+p2,p1.z);
}
LL v[600005]; int t;
int main(){
	scanf("%d%d",&N,&M);
	for(int i=2;i<=N+M;++i){
		int x; LL y;
		scanf("%d%lld",&x,&y);
		ins(x,i,y);
	}
	for(int i=N;i>=1;--i){
		t=0;
		for(int j=h[i];j;j=nxt[j]){
			st[++t]=f[to[j]]+w[j];
			v[2*t-1]=st[t].x;
			v[2*t]=st[t].y;
		}
		sort(v+1,v+t+t+1);
		f[i].x=v[t], f[i].y=v[t+1];
		for(int j=1;j<=t;++j){
			if(v[t]<st[j].x) f[i].z+=st[j].z+st[j].x-v[t];
			else if(v[t]>st[j].y) f[i].z+=st[j].z+v[t]-st[j].y;
			else f[i].z+=st[j].z;
		}
	}
	printf("%lld\n",f[1].z);
	return 0;
}

蒟蒻刚学OI，求助大佬

讨论操作

回复

相关推荐

蒟蒻刚学OI，求助大佬