ACM-ICPC 2017 Asia Shenyang

 L. Tree

题意:给出k个颜色和一棵树,要求在树上对每个节点进行染色,之后,对于每个颜色i,求一颗最小生成树Ei,最后问最大的 E1 ∩ E2 · · · ∩ Ek,也就是这些最小生成树最多有几条公共边

思路:

一开始想的是求出树的直径,贪心的从两边往里放,之后求中间的长度就是公共边长度。wa了,因为如果这个数是个海星一样的东西就没法贪心。

之后,想到拓扑排序,从外层往里层染色,也很容易的造出错误样例。

看了题解以后,

其实我们不必在意这些点到底是如何染色的,我们只需要遍历所有的边,对于一条边来说,如果它左边有大于等于k个端点,右边也有大于等于k个端点,那么这条边必定是可以的。

所以dfs搜边,回溯出每个点的左右两边各有多少端点即可。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string.h>
#include<set>
#include<map>
#include<vector>
using namespace std;
const double pi = 3.14159;
typedef long long int ll;
vector<int>v[200005];
int use[200005];
int s, t;
ll ans = 0;
int n, k;
void dfs(int index, int pre) {
    use[index] = 1;
    for (int i = 0; i<v[index].size(); i++) {
        if (v[index][i] != pre) {
            dfs(v[index][i], index);
            use[index] += use[v[index][i]];
        }
    }
    if (use[index] >= k&&n - use[index] >= k)
        ans++;
    return;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        scanf("%d%d", &n, &k);
        int a, b;
        for (int i = 1; i < n; i++) {
            scanf("%d%d", &a, &b);
            v[a].push_back(b);
            v[b].push_back(a);
        }
        dfs(1, 0);
        printf("%lld\n", ans);
        for (int i = 1; i <= n; i++) {
            v[i].clear();
        }
    }
    return 0;

}

 

上一篇:2019-2020 ICPC Asia Taipei-Hsinchu Regional Contest 训练记录


下一篇:The Preliminary Contest for ICPC Asia Shenyang 2019 G. Special necklace(物理求并联电阻阻值)