题目链接：https://ac.nowcoder.com/acm/problem/212004

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109689050

题目

众所周知，题目名称与题面没有任何关系。

你发现了一道 div2 的 A 题，下面是这道题的题面：

给定一张 个点， 条边的无向联通图和一个常数 ，每个点拥有点权 ，每条边拥有边权 ，现在他决定保留一些边，这样将剩余部分连通块，牛牛的目标是使得每个剩余的连通块的点权和都是 的倍数，同时最小化被保留的边的权值和。

输入

第一行两个正整数

接下来一行 个正整数，第 个正整数表示节点 的权值是

接下来 行，每行 个正整数，表示一条连接 边权为 的边。

输出

输出一行一个正整数最小的权值和。

样例输入1

5 2 
1 0 1 1 1
1 2 5
1 4 3
2 3 2
2 5 1

样例输出1

6

样例解释1

选择

样例输入2

10 3 
1 3 4 2 1 6 2 3 5 6
1 2 2
1 4 1
2 3 3
2 6 3
2 10 2
5 6 4
5 7 4
6 8 3
6 9 1

样例输出2

12

样例解释2

选择

数据范围

思路

这道题是一道爆搜。

因为原来就是一棵树，那我们就可以让任意一个点为根，进行 dfs 爆搜。

对于每一个子树，如果它自己已经可以单独存在，那它就没有必要与它的父亲连边。
否则，就要连边，与父亲变成新的连通块。

代码

#include<cstdio>
#include<queue>

using namespace std;

vector <int> to[1000001], size[1000001];
int n, k, x, y;
long long z, sum[1000001], ans;

void dfs(int now, int father) {
    for (int i = 0; i < to[now].size(); i++)
        if (father != to[now][i]) {
            dfs(to[now][i], now);
            sum[now] = (sum[now] + sum[to[now][i]]) % k;
            if (sum[to[now][i]]) ans += size[now][i];//如果这个子树不能单独形成连通块就要连接
        }
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
        sum[i] %= k;
    }

    for (int i = 1; i < n; i++) {
        scanf("%d %d %lld", &x, &y, &z);
        to[x].push_back(y);
        size[x].push_back(z);
        to[y].push_back(x);
        size[y].push_back(z);
    }

    dfs(1, 0);

    printf("%lld", ans);

    return 0;
}