题意

给定一个树，树上每个节点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;
}

 

原文地址：http://www.cnblogs.com/codingMIKU/p/16801011.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性