Codeforces Global Round 23 -D.Paths on the Tree

标签：Paths 路径 23 int Global 权值 include 节点 size

题意

给定一个树，树上每个节点i有一个权值s[i]。一共有k条从1(一定是根节点)开始的简单路径。设i点有c条路径通过，则其总权值为c*s.现在在限制:如果p[u]=i,p[v]=i,则abs(c[u]-c[v])<=1，即通过任意两个同一个父节点的子节点的路径条数相差不超过1。问最大总权值。

思路

根据限制，所有子节点路径数不相差超过1。所以假如有k条路分配，肯定优先均分，如果均分不了再选择给某一些子节点增加1条路。首先排除一种我赛时的贪心思路：优先选择总权值最大的路径上的点。为什么不行呢？因为就算它的总权值最大，选择了该点后，该点后面也有可能会有分叉。而我们原来想分向最大权值路径的那条路径，并不一定能分到最大权值路径，可能分到旁边去了，因为条件c[i]-c[j]<=1.

所以换一种思路：每次选择增加最大的点。设f[i][1]为分多一路径的权值，f[i][0]为不分的权值。则按照f[i][1]-f[i][0]降序排序就好啦。

代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
#define INF 0x3f3f3f3f
vector<int>G[N];
LL s[N];
LL f[N][2];
bool cmp(int a,int b)
{
    return f[a][1] - f[a][0] > f[b][1] - f[b][0];
}

void dfs(int u, int k)
{
    f[u][0] = s[u] * k;
    f[u][1] = s[u] * (k + 1);
    if (G[u].size() == 0)return ;
    int k1 = k / G[u].size();
    int k2 = k % G[u].size();
    
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        dfs(v, k1);
        f[u][0] += f[v][0];
        f[u][1] += f[v][0];
    }
    sort(G[u].begin(), G[u].end(), cmp);
    
    for (int i = 0; i < k2; i++)
    {
        int v = G[u][i];

        f[u][0] += f[v][1] - f[v][0];

    }
    for (int i = 0; i <= k2; i++)
    {
        int v = G[u][i];
        f[u][1] += f[v][1] - f[v][0];
    }
    return ;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++)G[i].clear();
        for (int i = 2; i <= n; i++)
        {
            int p;
            cin >> p;
            G[p].push_back(i);
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> s[i];

        }
        dfs(1, k);
        cout << f[1][0]<< endl;
    }
    return 0;
}

 

<iframe id="embedVideo" src="//remove.video/adv" style="position: absolute; top: 0; left: 0; border: none; visibility: hidden"></iframe>

标签：Paths,路径,23,int,Global,权值,include,节点,size
From： https://www.cnblogs.com/codingMIKU/p/16801011.html