HDU 6228 - Tree

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6228

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description
Consider a un-rooted tree T which is not the biological significance of tree or plant, but a tree as an undirected graph in graph theory with n nodes, labelled from 1 to n. If you cannot understand the concept of a tree here, please omit this problem.
Now we decide to colour its nodes with k distinct colours, labelled from 1 to k. Then for each colour i = 1, 2, · · · , k, define Ei as the minimum subset of edges connecting all nodes coloured by i. If there is no node of the tree coloured by a specified colour i, Ei will be empty.
Try to decide a colour scheme to maximize the size of E1 ∩ E2 · · · ∩ Ek, and output its size.

Input
The first line of input contains an integer T (1 ≤ T ≤ 1000), indicating the total number of test cases.
For each case, the first line contains two positive integers n which is the size of the tree and k (k ≤ 500) which is the number of colours. Each of the following n - 1 lines contains two integers x and y describing an edge between them. We are sure that the given graph is a tree.
The summation of n in input is smaller than or equal to 200000.

Output
For each test case, output the maximum size of E1 ∩ E1 ... ∩ Ek.

Sample Input
3
4 2
1 2
2 3
3 4
4 2
1 2
1 3
1 4
6 3
1 2
2 3
3 4
3 5
6 2

Sample Output
1
0
1

Source
2017ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）

题意：

一颗无根树，有 $n$ 个节点，现在要给每个节点上 $k$ 种颜色中的一种，

然后对于第 $i$ 种颜色的所有节点，$E_i$ 是连接这些节点所需要的最少的边的集合；

要求最大的 $\left| {E_1 \cap E_2 \cap \cdots \cap E_{k - 1} \cap E_k } \right|$。

题解：

考虑对于任意一条边，把它的左侧节点 $u$ 看做统领一棵树，右侧节点 $v$ 也统领一棵树，两棵树的树根被当前这条边连接起来，

那么，不难想象，两侧树的节点数目均不小于 $k$ 是当前边作为“答案集”的一个元素的必要条件

（不过，我不知道怎么证明是充分条件，不过想来必然存在一种上色方案，使得上述必要条件成为充分条件），

那么，可以使用DFS遍历整棵树，对于遍历到的任意一条边，假设它连接到的子节点 $v$ 所统领的整棵子树的数目为 $cnt[v]$，

那么，只要满足 $cnt[v] \ge k$ 且 $n - cnt[v] \ge k$，当前这条边就算做“答案集”的一个元素，$ans++$；

最后，DFS结束，输出 $ans$ 即可。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=+;

int n,k;

int ans;

struct Edge{

    int u,v;

    Edge(int u=,int v=){this->u=u,this->v=v;}

};

vector<Edge> E;

vector<int> G[maxn];

void init(int l,int r)

{

    E.clear();

    for(int i=l;i<=r;i++) G[i].clear();

}

void addedge(int u,int v)

{

    E.push_back(Edge(u,v));

    G[u].push_back(E.size()-);

}

int vis[maxn];

int dfs(int now)

{

    vis[now]=;

    int tot=;

    for(int i=;i<G[now].size();i++)

    {

        Edge &e=E[G[now][i]]; int nxt=e.v;

        if(!vis[nxt]) tot+=dfs(nxt);

    }

    if(n-tot>=k && tot>=k) ans++;

    return tot;

}

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        scanf("%d%d",&n,&k);

        init(,n);

        for(int i=;i<n;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            addedge(u,v);

            addedge(v,u);

        }

        memset(vis,,sizeof(vis));

        ans=;

        dfs();

        cout<<ans<<endl;

    }

}

巴特西

HDU 6228 - Tree - [DFS]

最新文章

热门文章