Enterprise520's blog

By Enterprise520, history, 5 weeks ago, In English,

CF911F5

This is my code. Help me please! I know people in Codeforces are helpful people.

include

include

include

include

include

include

include

include

include

include

define int long long

using namespace std;

const int maxn=200010;

int n,head[maxn],cnt,qidian=1,zhongdian=1,dis[maxn][3];

int zhijingshangdedian[maxn],ans,zhijing[maxn],du[maxn],fa[maxn],len,root=1,chudu[maxn];

struct edge

{

int to,next;

}e[maxn<<1];

queueq;

inline int read()

{

int x=0,f=1;

char ch=getchar();

while(ch<'0'||ch>'9')

{

   if(ch=='-')

 f=-1;

ch=getchar();

}

while(ch>='0'&&ch<='9')

{

x=(x<<1)+(x<<3)+(ch^48);

ch=getchar();

}


return x*f;

}

inline void write(int a)

{

if(a<0)

{

char a='-',b='1';

putchar(a);

putchar(b);

}

else

{

if(a>=10)

write(a/10);

putchar(a%10+'0');

}

}

void add(int from,int to)

{

e[++cnt]=(edge){to,head[from]};

head[from]=cnt;

}

void dfs(int now,int father,int cishu)

{

if(!cishu)

fa[now]=father;

for(int i=head[now];i;i=e[i].next)

{

int to=e[i].to;

if(to==father)

continue;

if(!cishu)

chudu[now]++;

dis[to][cishu]=dis[now][cishu]+1;

dfs(to,now,cishu);

}

}

int xunzhaozhijing(int now,int father)

{

if(now==zhongdian)

{

zhijingshangdedian[now]=1;

zhijing[1]=now;

return 1;

}

for(int i=head[now];i;i=e[i].next)

{

int to=e[i].to;

if(to==father)

continue;

int check=xunzhaozhijing(to,now);

if(check)

{

zhijingshangdedian[now]=1;

 zhijing[check+1]=now;

 return check+1;

}

}

return 0;

}

signed main()

{

n=read();

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

{

int u=read(),v=read();

add(u,v),add(v,u);

du[u]++,du[v]++;

}

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

if(du[i]>1)

{

root=i;

 break;

}

dfs(root,0,0);

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

if(dis[i][0]>dis[qidian][0])

qidian=i;

dfs(qidian,0,1);

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

if(dis[i][1]>dis[zhongdian][1])

zhongdian=i;

dfs(zhongdian,0,2);

xunzhaozhijing(qidian,0);

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

if(!zhijingshangdedian[i])

ans+=max(dis[i][1],dis[i][2]);

len=dis[qidian][2]+1;

// write(len),puts("");

ans+=len*(len-1)/2;

write(ans),puts(""); 

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

if(!chudu[i]&&!zhijingshangdedian[i])

q.push(i);

zhijingshangdedian[0]=1;

while(!q.empty())

{

int now=q.front();

q.pop();

write(now),putchar(' ');

if(dis[now][1]>dis[now][2])

write(qidian),putchar(' '),write(now);

else

write(zhongdian),putchar(' '),write(now);

puts("");

chudu[fa[now]]--;

if(!chudu[fa[now]]&&!zhijingshangdedian[fa[now]])

q.push(fa[now]);

}

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

write(qidian),putchar(' '),write(zhijing[i]),putchar(' '),write(zhijing[i]),puts("");

return 0;

}

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You code is a mess, no one will be able to help you here, upload it on github or one pasteio or something

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Enterprise520 (previous revision, new revision, compare).