CF1363E Tree Shuffling 题解

description：

solution：

我们观察到这棵树的一个性质：一个节点可以完成某修改操作，那么它的祖先也可以完成。

所以我们可以先优化题目的策略：遇到祖先节点的 $a$ 值比子节点小的时候直接把子节点的值更新成这个 $a$ 即可。（效果上是相等的）

优化完了之后直接 dp 即可。

我们设 $dp[u][0]$ 表示 $u$ 节点的子树中初始状态为 $0$ 且准备改为 $1$ 的节点的个数。 $dp[u][1]$ 同理。

那么对于子树的更改我们就可以一步一步记录到祖先节点上，最终累加判断就行了。

盘点自己的一个很小但找了很久的 bug：

u 和 i 在键盘上离得太近导致在 i 的循环内错打为 u。

code：

#include<cstdio>
//#include<algorithm>
#include<vector>
using namespace std;
struct ben
{
	long long x,y,z;
}a[200005];
vector<long long>e[200005];
long long ans;
long long dp[200005][2];
long long min(long long x,long long y)
{
	if(x>y)return y;
	return x;
}
void dfs(long long u,long long fa,long long sp)
{
	if(a[u].y!=a[u].z)
	{
		dp[u][a[u].y]=1;
	}
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fa)continue;
		dfs(v,u,min(a[u].x,sp));
		dp[u][0]+=dp[v][0];
		dp[u][1]+=dp[v][1];
	}
	sp=min(sp,a[u].x);
	long long sum=min(dp[u][0],dp[u][1]);
	ans+=2*sum*sp;
	dp[u][0]-=sum;
	dp[u][1]-=sum;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	}
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	dfs(1,-1,0x3f3f3f3f);
	if(dp[1][0]||dp[1][1])ans=-1;
	printf("%lld\n",ans);
	return 0;
}