**CF911F5**↵
------↵
This is my code.↵
Help me please!↵
I know people in Codeforces are helpful people.↵
↵
#include<cmath>↵
↵
#include<cstdio>↵
↵
#include<iostream>↵
↵
#include<cstdlib>↵
↵
#include<algorithm>↵
↵
#include<cstring>↵
↵
#include<map>↵
↵
#include<queue>↵
↵
#include<set>↵
↵
#include<vector>↵
↵
#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];↵
↵
queue<int>q;↵
↵
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;↵
}↵
}↵
------↵
This is my code.↵
Help me please!↵
I know people in Codeforces are helpful people.↵
↵
#include<cmath>↵
↵
#include<cstdio>↵
↵
#include<iostream>↵
↵
#include<cstdlib>↵
↵
#include<algorithm>↵
↵
#include<cstring>↵
↵
#include<map>↵
↵
#include<queue>↵
↵
#include<set>↵
↵
#include<vector>↵
↵
#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];↵
↵
queue<int>q;↵
↵
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;↵
}↵
