CF1466D 13th Labour of Heracles

希腊神话

13th Labour of Heracles

文化（神话）常识

百度来的

赫拉克勒斯（Heracles）是宙斯和阿尔克墨涅所生的儿子（而阿尔克墨涅是珀耳修斯的孙女，底比斯国王安菲特律翁的妻子，太乱了），不过不重要

关于他的经历自己看baidu吧，跟言情小说似的，太长了

总而言之，它作为半人半神，在人间做了许许多多事，其中以他的十二个功绩为最

题目大意

又要靠我自己翻译

给定一棵 $n$ （ $n \le 2 \times 10^5$ ）个点带权树，有以下定义：

我们用 $k$ 种颜色将树的边染色（可以不用尽 $k$ 种颜色），保证每条边有且只有一种颜色，我们称其为“ $k$ 染色”
对于一个颜色 $x$ ，定义“ $x$ 色块”为只由颜色为 $x$ 的边和其连接的点组成的极大连通块，明显，在这种定义下，块内没有度为 $0$ 的点
一个色块的权值定义为该块中所有点的权值和（两个不同块可以包含同一个点）， $x$ 色块的权值定义为所有 $x$ 色块中最大的一个，若不存在 $x$ 色块则权值为 $0$
对于树的一个 $k$ 染色，其权值为所有属于 $k$ 的 $x$ 色块的权值和

现在，对于 $1 \sim n - 1$ 的每一个 $k$ ，要求出该树的最大 $k$ 染色权值

注意有多组数据， $T \le 10^5$ ，时限 $2.5s$

思路

有个鬼的思路啊， $T \le 10^5, n \le 10^5$ ，读入都挂了吧！

先假设我们读入了，考虑问题

首先对于一个最大的 $k$ 染色，它的每一个颜色一定只对应一个色块，因为有多个色块的话只取最大，必然会有点的权值被浪费

再考虑任意两个直接相连的色块，它们一定有且只有一个“割点”，这个点的权值被计算了两次，我们当然是让这个点的权值尽可能的大

考虑将点排序， $k = 1$ 时答案就是所有的和，每次加 $1$ 后就加一个当前最大点，但一个点只能被加 $deg$ 遍

然后突然发现，原来题目保证了 $\sum n \le 2 \times 10^5$ ，读入不成问题！真是纸老虎啊

#include <bits/stdc++.h>
#define STC static
#define LL long long
using namespace std;
const int N = 1e5 + 5;

struct Node
{
    int deg, w;
    bool operator < (const Node &t) const
    {
        return w == t.w ? deg > t.deg : w > t.w;
    }
} ;
int main()
{
    int T;
    scanf("%d", &T);
    int n;
    LL ans;
    STC Node a[N];
    while (T--)
    {
        scanf("%d", &n);
        ans = 0;
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i].w), ans += a[i].w, a[i].deg = -1;
        for (int i = 1, u, v; i < n; ++i)
            scanf("%d %d", &u, &v), ++a[u].deg, ++a[v].deg;
        sort(a + 1, a + 1 + n);
        printf("%lld", ans);
        for (int i = 2, now = 1; i < n; ++i)
        {
            while (!a[now].deg)
                ++now;
            --a[now].deg;
            ans += a[now].w;
            printf(" %lld", ans);
        }
        puts("");
    }
    return 0;
}