| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为毛我的链表也跪了 TLE#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
struct point{
int n;
point* next;
void init(int nn){
n=nn;
next=NULL;
}
}*p;
struct link{
point *head,*last;
void init(){
head=new point;
head->init(0);
last=head;
}
void push(point *p){
last->next=p;
last=p;
}
}l[50010];
int n,s,t,b[50010],son[50010],i,mn=2147483647;
bool vd[50010];
void DFS(int x){
vd[x]=true;
son[x]=0;
b[x]=0;
int u;
point *p=l[x].head->next;
while (p){
u=p->n;
if (vd[u]) {
p=p->next;
continue;
}
DFS(u);
son[x]+=son[u]+1;
b[x]=max(b[x],son[u]+1);
p=p->next;
}
b[x]=max(b[x],n-son[x]-1);
mn=min(mn,b[x]);
}
int main(){
srand(time(0));
scanf("%d",&n);
for(i=1;i<=n;i++) l[i].init();
for(i=1;i<n;i++) {
scanf("%d%d",&s,&t);
p=new point;
p->init(t);
l[s].push(p);
p=new point;
p->init(s);
l[t].push(p);
}
DFS(rand()%n+1);
for(i=1;i<=n;i++)
if (mn==b[i]){
printf("%d ",i);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator