\u7ecf\u5178\u7684\u6709\u70b9\u6c34\u7684\u6811DP\u4e86\u3002\u3002
\u8bbeS[x]\u4e3a\u4ee5\u8282\u70b9x\u4e3a\u8ddf\u7684\u5b50\u6811\u7684\u5927\u5c0f\u3002\u3002
\u753b\u4e2a\u56fe\u4fbf\u53ef\u77e5\u53bb\u6389x\u53ef\u5272\u51fa\u7684\u6700\u5927\u5757\u662f\u4ed6\u7684\u5168\u4f53\u51cf\u53bb\u4ed6\u81ea\u5df1\u7684\u5927\u5c0f\u548c\u4ed6\u7684\u6700\u5927\u5b50\u6811\u7684\u6700\u5927\u503c\u3002\u3002\u3002
P.S
\u4e00\u5b9a\u8981\u7528\u524d\u5411\u661f\u963f\u3002\u3002
\u6211\u4e00\u76f4\u662f\u90bb\u63a5\u8868\u7684\u5fe0\u5b9e\u62e5\u62a4\u8005\u3002\u3002\u4e0d\u8fc7\u8fd9\u6b21\u6211\u53d7\u632b\u4e86\u3002\u3002
\u6211\u771f\u4e0d\u660e\u767d\uff0c\u524d\u5411\u661f\u662f\u8981\u6392\u5e8f\u7684\u3002\u3002\u6211\u7528stl\u662fnlogn\u3002\u3002\u90bb\u63a5\u8868\u518d\u600e\u4e48\u5783\u573e\u4e5f\u662fO\uff08n\uff09\u7684\u963f\uff01\uff01\u3002\u3002
\u600e\u4e48\u4e00\u4e2a52ms\u4e00\u4e2a1600+ms\u3002\u3002\u5929\u963f\uff01\uff01\uff01\uff01
Code\u3002\u3002\u3002
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=16000;
int N,cnt=0;
int H[maxn+2]={0};
\/\/graph
struct edge
{
int s,t;
}E[maxn*2];
bool cmp(const edge&x,const edge&y)
{ return x.s<y.s;}
void add(int s,int t)
{
E[cnt].s=s;E[cnt].t=t;cnt++;
E[cnt].s=t;E[cnt].t=s;cnt++;
}
void init()
{
scanf("%d",&N);
int s,t;
for(int i=1;i<N;i++)
{
scanf("%d %d",&s,&t);
add(s,t);
}
sort(E,E+cnt,cmp);
for(int i=0;i<cnt;i++)
H[E[i].s+1]++;
for(int i=2;i<=N+1;i++)
H[i]+=H[i-1];
}
\/\/solve
int ans=maxn+1,acnt=0;
int Ans[maxn+1];
int S[maxn+1]={0};
bool Vis[maxn+1]={0};
int dfs(int x)
{
Vis[x]=true;int Max=0;
for(int i=H[x];i<H[x+1];i++)
{
int o=E[i].t;
if(!Vis[o])
{
S[x]+=dfs(o);
Max=max(Max,S[o]);
}
}
S[x]++;
Max=max(Max,N-S[x]);
if(Max<ans)
ans=Max,Ans[0]=x,acnt=1;
else if(Max==ans)
Ans[acnt++]=x;
return S[x];
}
int main()
{
init();
dfs(1);
cout<<ans<<" "<<acnt<<endl;
sort(Ans,Ans+acnt);
cout<<Ans[0];
for(int i=1;i<acnt;i++)
cout<<" "<<Ans[i];
cout<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u7ecf\u5178\u7684\u6709\u70b9\u6c34\u7684\u6811DP\u4e86\u3002\u3002\u8bbeS[x]\u4e3a\u4ee5\u8282\u70b9x\u4e3a\u8ddf\u7684\u5b50\u6811\u7684\u5927\u5c0f\u3002\u3002\u753b\u4e2a\u56fe\u4fbf\u53ef\u77e5\u53bb\u6389x\u53ef\u5272\u51fa\u7684\u6700\u5927\u5757\u662f\u4ed6\u7684\u5168\u4f53\u51cf\u53bb\u4ed6\u81ea\u5df1\u7684\u5927\u5c0f\u548c\u4ed6\u7684\u6700\u5927\u5b50\u6811\u7684\u6700\u5927\u503c\u3002\u3002\u3002P.S\u4e00\u5b9a\u8981\u7528\u524d\u5411\u661f\u963f\u3002\u3002\u6211\u4e00\u76f4\u662f\u90bb\u63a5\u8868\u7684\u5fe0\u5b9e\u62e5\u62a4\u8005\u3002\u3002\u4e0d\u8fc7\u8fd9\u6b21\u6211\u53d7\u632b\u4e86\u3002\u3002\u6211\u771f\u4e0d\u660e\u767d\uff0c\u524d\u5411\u661f\u662f\u8981\u6392\u5e8f\u7684\u3002\u3002\u6211\u7528stl\u662fnlogn\u3002\u3002\u90bb\u63a5\u8868\u518d\u600e\u4e48\u5783\u573e\u4e5f\u662fO\uff08n\uff09\u7684\u963f\uff01\uff01\u3002\u3002\u600e\u4e48\u4e00\u4e2a52ms\u4e00\u4e2a1600+ms\u3002\u3002\u5929\u963f\uff01\uff01\uff01\uff01Code\u3002\u3002\u3002#include<iostream>#include<string.h>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=16000;int N,cnt=0;int H[maxn+2]={0};\/\/graphstruct edge{int s,t;}E[maxn*2];bool cmp(const edge&x,const edge&y){ return x.s<y.s;}void add(int s,int t){E[cnt].s=s;E[cnt].t=t;cnt++;E[cnt].s=t;E[cnt].t=s;cnt++;}void init(){scanf("%d",&N);int s,t;for(int i=1;i<N;i++){scanf("%d %d",&s,&t);add(s,t);}sort(E,E+cnt,cmp);for(int i=0;i<cnt;i++)H[E[i].s+1]++;for(int i=2;i<=N+1;i++)H[i]+=H[i-1];}\/\/solveint ans=maxn+1,acnt=0;int Ans[maxn+1];int S[maxn+1]={0};bool Vis[maxn+1]={0};int dfs(int x){Vis[x]=true;int Max=0;for(int i=H[x];i<H[x+1];i++){int o=E[i].t;if(!Vis[o]){S[x]+=dfs(o);Max=max(Max,S[o]);}} S[x]++;Max=max(Max,N-S[x]);if(Max<ans) ans=Max,Ans[0]=x,acnt=1;else if(Max==ans)Ans[acnt++]=x;return S[x]; }int main(){init();dfs(1);cout<<ans<<" "<<acnt<<endl;sort(Ans,Ans+acnt);cout<<Ans[0];for(int i=1;i<acnt;i++)cout<<" "<<Ans[i];cout<<endl;}<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/651"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=651"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/651\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=651"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=651"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=651"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}