# @codeforces - 1205D@ Almost All

2019/08/23 20:54

[toc]

## @description@

Input 第一行包含一个整数 n (1≤n≤1000) 表示结点数。 接下来 n-1 行每行两个整数 u, v (1≤u,v≤n, u≠v)，表示树上有一条边 (u, v)。

Output 输出 n-1 行，每行形如 u v x (0≤x≤10^6)，表示 (u, v) 这条边的边权定为 x。 可以按任意顺序输出每条边的权值。

Examples Input 3 2 3 2 1 Output 3 2 1 1 2 2

Input 4 2 4 2 3 2 1 Output 4 2 1 3 2 2 1 2 3

Input 5 1 2 1 3 1 4 2 5 Output 2 1 1 5 2 1 3 1 3 4 1 6

## @accepted code@

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 2000;
struct Graph{
struct edge{
int to, val, tag;
edge *nxt, *rev;
}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt;
Graph() {ecnt = &edges[0];}
void addedge(int u, int v, bool flag = true) {
edge *p = (++ecnt), *q = (++ecnt);
p->to = v, p->tag = flag, p->nxt = adj[u], adj[u] = p;
q->to = u, q->tag = flag, q->nxt = adj[v], adj[v] = q;
p->rev = q, q->rev = p;
//		printf("! %d %d %d\n", u, v, flag);
}
}G1, G2;
int fa[MAXN + 5], n, m;
void rebuild(int x, int f) {
int lst = x; fa[x] = f;
if( p->to == f ) continue;
rebuild(p->to, x);
int nw = (++m);
lst = nw;
}
}
int siz[MAXN + 5];
void update(Graph::edge *&a, Graph::edge *b, int tot) {
if( a == NULL ) a = b;
else if( b != NULL && max(siz[a->to], tot-siz[a->to]) > max(siz[b->to], tot-siz[b->to]) )
a = b;
}
Graph::edge *get_mid_edge(int x, int f, int tot) {
Graph::edge *ret = NULL; siz[x] = (x <= n);
if( p->to == f ) continue;
update(ret, get_mid_edge(p->to, x, tot), tot);
update(ret, p, tot);
siz[x] += siz[p->to];
}
return ret;
}
int cnt, type, tag;
void dfs(int x, int f, bool flag, int k) {
if( x <= n && (!flag) ) cnt++;
if( p->to == f ) continue;
if( !p->tag && p->to < x ) dfs(p->to, x, flag, k);
}
if( p->to == f ) continue;
if( p->tag ) {
p->val = p->rev->val = (cnt - k)*type;
dfs(p->to, x, false, cnt);
}
else if( !p->tag && p->to > x ) dfs(p->to, x, flag, k);
}
}
int main() {
scanf("%d", &n); m = n;
for(int i=1;i<n;i++) {
int u, v; scanf("%d%d", &u, &v);
}
rebuild(1, 0);
Graph::edge *e = get_mid_edge(1, 0, n);
if( e ) {
if( e->tag ) e->val = e->rev->val = 1;
type = 1, cnt = 1, dfs(e->to, e->rev->to, true, 0);
type = siz[e->to], cnt = 1, dfs(e->rev->to, e->to, true, 0);
}
for(int i=2;i<=n;i++)
if( p->tag ) printf("%d %d %d\n", i, fa[i], p->val);
}


0
0 收藏

0 评论
0 收藏
0