@codeforces - 1205D@ Almost All

2019/08/23 20:54
阅读数 11

[toc]


@description@

给定一个 n 个点的无向树。

请在每条边上写上权值,使得对于每一个满足 1 <= x <= $\lfloor\frac{2*n^2}{9}\rfloor$ 的 x,存在一对 (i, j) 使得 i, j 的距离等于 x。

保证解总是存在。

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

@solution@

看到分母中含有因子 3,又看到了这是棵树,会想到什么。 反正我是想到了边分治的时间复杂度中有个什么分母的因子有 3,于是就着手从边分治的角度开始构造。

先考虑几种比较特殊的树:

对于菊花图(即除了根以外所有点都是根的儿子),此时路径长度要么 = a[x],要么 = a[x] + a[y]。 通过两个数相加得到 O(n^2) 范围的数,可以联想到类似于 “大步小步” 的方法。 将根的儿子分为两半,一半连根的长度为 1, 2, ..., n/2,另一半连根的长度为 1*(n/2), 2*(n/2), ... (n/2)*(n/2)。可以直观地得到这样的构造是合法的。

对于链,我们同样是考虑类似于 “大步小步” 的方法,取链的中点将链分为两半,左半段所有边权值为 1,右半段所有边权值为 n/2。则所有跨越链中点的路径就可以满足题意的限制。

上面两个特例,都有两点相似的地方:将边集分为两部分;通过类 “大步小步” 的方法构造权值。 注意到 2/9 = 2/3*1/3,我们是否可以对于任意的树,将边集分为 2/3 与 1/3 的两部分,然后再通过上述方法构造权值呢? 如果使用我在开头所说的边分治中重构树的方法,是可以做到的。

我们考虑这样重构:对于点 x,假如它含有儿子 p1, p2, ... pk,我们建 k 个虚点 q1, q2, ... qk,并建虚边连成 x -> q1 -> q2 -> ... -> qk;之后,我们再建 k 条实边,第 i 条连 qi -> pi。实边 i 的权值对应着原图 x -> pi 的权值。 然后我们找一条边 e,使得 e 的左右两端连接的实点数量最接近。注意按上述方法重构出来的树才能保证两部分的数量最大差异为 1/3 与 2/3,因为实点的度数最大为 2(如果其他方法可能会出现比 1/3 小 1、比 2/3 大 1 的极端情况)。

怎么分配实边的边权呢?可以考虑从 e 的两端进行 dfs,维护当前已经经过了多少实点 cnt 与当前结点到根的路径上边权和 sum。 假如遇到一个实边,则分配 cnt - sum 的边权给实边即可。如果是 “大步” 部分就多乘一个系数(即 “小步” 部分的 siz)即可。

但是这种构造方法有一些细节,比如我 dfs 时在一个虚点,则尽量先往父亲那边跑(因为虚点到父亲点之间的路径没有任何实边);以及 e 是实边时,要给 e 分配 1 的边权;以及当我 dfs 到一个点如果没有经过任何实边,则不应该将这个点算入 cnt。 至于以上实现的正确性,其实是要分类讨论讨论出来的(可能有更细节的地方,参见代码)。

@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;
	for(Graph::edge *p=G1.adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		rebuild(p->to, x);
		int nw = (++m);
		G2.addedge(lst, nw, false);
		G2.addedge(nw, p->to);
		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);
	for(Graph::edge *p=G2.adj[x];p;p=p->nxt) {
		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++;
	for(Graph::edge *p=G2.adj[x];p;p=p->nxt) {
		if( p->to == f ) continue;
		if( !p->tag && p->to < x ) dfs(p->to, x, flag, k);
	}
	for(Graph::edge *p=G2.adj[x];p;p=p->nxt) {
		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);
		G1.addedge(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++)
		for(Graph::edge *p=G2.adj[i];p;p=p->nxt)
			if( p->tag ) printf("%d %d %d\n", i, fa[i], p->val);
}

@details@

虽然官方题解不是这个,但我觉得,使用边分治重构树的技巧进行构造还是很有趣的。

只是细节超级多,试了好久才勉强写出来一个比较简洁的正确代码。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部