Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 为毛我的链表也跪了 TLE

Posted by logos_mhr at 2015-08-20 09:29:16 on Problem 3107
```#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;
void init(){
}
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;
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: