题解 CF1363E 【Tree Shuffling】
ShineEternal
2020-06-07 17:49:52
[更佳更完整的阅读效果。](https://vipblog.github.io/F7QMFSJu-/)
## description：
## solution：
我们观察到这棵树的一个性质：一个节点可以完成某修改操作，那么它的祖先也可以完成。
所以我们可以先优化题目的策略：遇到祖先节点的 $a$ 值比子节点小的时候直接把子节点的值更新成这个 $a$ 即可。（效果上是相等的）
优化完了之后直接 dp 即可。
我们设 $dp[u][0]$ 表示 $u$ 节点的子树中初始状态为 $0$ 且准备改为 $1$ 的节点的个数。 $dp[u][1]$ 同理。
那么对于子树的更改我们就可以一步一步记录到祖先节点上，最终累加判断就行了。
----
盘点自己的一个很小但找了很久的 bug：
u 和 i 在键盘上离得太近导致在 i 的循环内错打为 u。
## code：
```cpp
#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;
}
```