@codeforces - 1205D@ Almost All

妖狐艹你老母 2023-06-01 13:59 8阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @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@ ##

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

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

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11402580.html