CF1187E Tree Painting(CF1187E Tree Painting)

CF1187E Tree Painting

分析

首先,我们贪心的想,当第一个点确定后,我们所求的最大值就是,依次选择子节点

这样,我们可以用树形DP求出以为根的树,所能得到的最大权值。

1

递推公式为

则,我们可以轻松得到

但是我们需要求出以每个点为根节点能得到的最大值的最大值

当然不难想到,用换根DP啦。

推换根DP的公式

子节点son

分为两部分,前边为原本下边的,后边的是,将父节点变为子节点后的贡献。

son

我们开始对式子进行拼接变形。

其中分别加原因是为了是把那一个Σ处理一下。

sz[son]

式子最后变为

好嘞,直接看代码。

Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int h[N],ne[N<<1],e[N<<1],idx;
LL f[N],g[N],sz[N];
int n;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs1(int u,int fa)
{
    sz[u] = 1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa) continue;
        dfs1(j,u);
        sz[u] += sz[j];
        f[u] += f[j];
    }
    f[u] += sz[u];
}

void dfs2(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa) continue;
        g[j] = g[u] + n - 2 * sz[j];
        dfs2(j,u);
    }
}

int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,-1);
    g[1] = f[1];
    dfs2(1,-1);
    LL ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans,g[i]);
    printf("%lld\n",ans);
    return 0;
}
————————

CF1187E Tree Painting

analysis

First of all, we greedily think that when the first point is determined, the maximum value we want is to select the child nodes < / strong >

In this way, we can use the < strong > tree DP < / strong > to find the maximum weight that can be obtained for the tree that is the root.

1

The recurrence formula is

Then we can easily get

However, we need to < strong > find the maximum value that can be obtained by taking each point as the root node < / strong >

Of course, it’s not hard to think of using < strong > for DP < / strong >.

Push the formula of root DP

子节点son

It is divided into two parts. The front part is the original lower part, and the back part is the contribution after changing the parent node into a child node.

son

We began to splice and deform the formula.

The reason is to add that one Σ Take care of it.

sz[son]

The formula finally becomes

OK, just look at the code.

Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int h[N],ne[N<<1],e[N<<1],idx;
LL f[N],g[N],sz[N];
int n;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs1(int u,int fa)
{
    sz[u] = 1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa) continue;
        dfs1(j,u);
        sz[u] += sz[j];
        f[u] += f[j];
    }
    f[u] += sz[u];
}

void dfs2(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j==fa) continue;
        g[j] = g[u] + n - 2 * sz[j];
        dfs2(j,u);
    }
}

int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,-1);
    g[1] = f[1];
    dfs2(1,-1);
    LL ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans,g[i]);
    printf("%lld\n",ans);
    return 0;
}