HDU 6228 tree 简单思维树dp

一、前言

前两天沈阳重现，经过队友提点，得到3题的成绩，但是看到这题下意识觉得题目错了，最后发现实际上是题目读错了。。。。GG

感觉自己前所未有的愚蠢了。。。。不过题目读对了也是一道思维题，但是很好理解。

二、题意

对于一个无相无环图，要求找出若干边，满足“这些边被至少K个不同的点集在互相联通的时候访问到”。或者说“这些边都包含在K个不同的点集个字组成的联通快里面”。

三、题解

考虑如何表示一个边，以及这条边两边的点的数量？（这是一棵树）
作为一颗树，就有树边概念，因而可以认为“该树包括他自己在内在树的一边”，“其他节点在树边的另一边”

因而，统计下，有多少符合要求的树边就可以了。具体实现见代码：

 #include<bits/stdc++.h>

 using namespace std;

 const long long MAXN=+;

 int child[MAXN];

 vector<int>G[MAXN];

 long long n,k;

 long long ans=;

 void dfs(int now,int last)

 {

     int len=G[now].size();

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

     {

         int tar=G[now][i];

         if(tar==last)continue;

         dfs(tar,now);

         child[now]+=child[tar];

     }    child[now]++;

     if(child[now]>=k&&n-child[now]>=k)ans++;

 }

 void init()

 {

 //    memset(child,0,sizeof(child));

     ans=;

     cin>>n>>k;

     for(int i=;i<=n;++i)G[i].clear(),child[i]=;

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

     {

         int a,b;

         cin>>a>>b;

         G[a].push_back(b);

         G[b].push_back(a);

     }

     dfs(,);

     cout<<ans<<endl;

 }

 int main()

 {

     cin.sync_with_stdio(false);

     int ca;cin>>ca;

     while(ca--)init();

     return ;

 }