HDU 6060 RXD and dividing

真是哭了，今天多校的图论题，算得上是在比赛的时候的进阶题目，A了这道就能挤开一大片那种……

没A，思路错了……

题意：
给你一棵树，要你将 { 2，3，4……n } 进行划分成 k 个集合，每个集合与{ 1 }相并后 求 最小 斯坦纳树，求和的最大值。

思路：
考虑每条边贡献值，只可能是 k 与 子树结点的最小值，将贡献值与边长相乘累加后便是答案。原因yy即可。
一边dfs得出每个结点的子树结点数，复杂度 O ( n ) 。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
int head[maxn];
int pre[maxn], num[maxn];
ll ans;

int n, idx, m;

struct node {
    int to, weight, next;
} edges[maxn << 1];

void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].weight = w;
    edges[idx].next = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    idx = ans = 0;
}

int dfs(int u, int p)
{
    num[u] = 1;
    for (int id = head[u]; ~id; id = edges[id].next)
        if (edges[id].to != p) {
            pre[edges[id].to] = edges[id].weight;
            num[u] += dfs(edges[id].to, u);
        }
    ans += min(num[u], m) * 1LL * pre[u];
    return num[u];
}

int main()
{
    int u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        dfs(1, 0);
        printf("%lld\n", ans);
    }
    return 0;
}