题解 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;
} 

发表于 2020-06-07 17:49:52 in 题解