@codeforces - 418D@ Big Problems for Organizers

布满荆棘的人生 2023-06-01 12:59 5阅读 0赞

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

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

## @description@ ##

n 个点连成一棵树，经过每条边需要花费 1 个单位时间。  
现给出 m 次询问，每次询问给出两个点，需要求所有点同时出发，最终所有点到达这两个点之一的最小花费时间。

**input**  
第一行包含一个整数 n (2 ≤ n ≤ 100000) ，表示点数。  
接下来 n-1 行每行两个 1~n 的整数，描述一条边。  
接下来包含一个整数 m，表示询问数。  
接下来 m 行每行两个整数，表示我们每次询问的两个点。

**output**  
对于每组询问，输出最少的时间。

**Examples**  
**Input1**  
3  
2 3  
3 1  
3  
2 1  
2 3  
3 1  
**Output1**  
1  
1  
1  
**Input2**  
4  
1 4  
1 2  
2 3  
3  
1 4  
1 3  
2 3  
**Output2**  
2  
1  
2

## @solution@ ##

假设询问给出的是 u, v 两个点，每个点肯定是往 u, v 中离自己更近的点移动。  
因此，我们总可以选择 u, v 的中心边，中心边连着的包含 u 的连通块向 u 移动，中心边连着的包含 v 的连通块向 v 移动。  
假如偶数长度，有多个中心边，任取一条即可。

实际上，相当于将中心边割断，然后分别以 u, v 为根求最远点。  
这个显然可以 lct 搞，不过我们还是不要搞那么复杂（其实也不复杂）。

考虑使用树链剖分能否维护（其实因为没有修改可以直接树上倍增）。不妨假设 u 的深度大于等于 v 的深度。

可以发现我们总可以找一条中心边使这个中心边在 u 到 lca(u, v) 的路径上。  
因此，对于 u 来说，它的路径仅分为直接往下和先上后下两种。先上后下可以通过记录 -dep\[x\] + x不经过重儿子的最远点距离 的最大值即可。  
而上面那个可以通过记录 x 向下的最长路径、次长路径即可得到，可以发现这样我们跳轻边时也容易得到答案。

而对于 v，我们需要分类讨论：  
（1）假如 v 是 u 的祖先，v 的路径分为向上，向下但不经过中心边两种。这个时候我们再统计 dep\[x\] + x不经过重儿子的最远点距离 的最大值即可。  
（2）否则，v 的路径分为直接往下、向上但不经过 lca 再向下、向上到达 lca 再向下、向上穿过 lca 继续向上、向上到达 lca 再转向 u 的方向向下但不经过中心边五种。  
注意我们要把 “向上到达 lca 再向下” 这种情况单独提出来求解，因为 lca 向下有两条禁止通行的路径。此时我们还需要记录第三长的路径。

维护最大值直接写 st 表，可以做到 O((n + m)logn)，因为树剖本身常数小所以跑得比 lct 和倍增都要快。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 100000; const int INF = (1<<30); struct edge{ edge *nxt; int to; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0]; void addedge(int u, int v) { edge *p = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p; p = (++ecnt); p->to = u, p->nxt = adj[v], adj[v] = p; } int siz[MAXN + 5], dep[MAXN + 5], hvy[MAXN + 5], fa[MAXN + 5]; void dfs1(int x, int f) { siz[x] = 1, dep[x] = dep[f] + 1, hvy[x] = 0, fa[x] = f; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs1(p->to, x); siz[x] += siz[p->to]; if( siz[p->to] > siz[hvy[x]] ) hvy[x] = p->to; } } int top[MAXN + 5], dfn[MAXN + 5], tid[MAXN + 5], dcnt = 0; void dfs2(int x, int tp) { top[x] = tp, dfn[++dcnt] = x, tid[x] = dcnt; if( hvy[x] ) dfs2(hvy[x], tp); for(edge *p=adj[x];p;p=p->nxt) { if( p->to == fa[x] || p->to == hvy[x] ) continue; dfs2(p->to, p->to); } } int f[MAXN + 5], g[MAXN + 5], h[MAXN + 5]; int pf[MAXN + 5], pg[MAXN + 5]; void dfs3(int x) { f[x] = g[x] = h[x] = 0; for(edge *p=adj[x];p;p=p->nxt) { if( p->to == fa[x] ) continue; dfs3(p->to); if( f[p->to] + 1 > f[x] ) { h[x] = g[x], g[x] = f[x], f[x] = f[p->to] + 1; pg[x] = pf[x], pf[x] = p->to; } else if( f[p->to] + 1 > g[x] ) { h[x] = g[x], g[x] = f[p->to] + 1; pg[x] = p->to; } else if( f[p->to] + 1 > h[x] ) h[x] = f[p->to] + 1; } } int lca(int u, int v) { while( top[u] != top[v] ) { if( dep[top[u]] < dep[top[v]] ) swap(u, v); u = fa[top[u]]; } if( dep[u] < dep[v] ) swap(u, v); return v; } int get_fa(int u, int d) { while( dep[top[u]] > d ) u = fa[top[u]]; return dfn[tid[u] - (dep[u] - d)]; } int st[2][20][MAXN + 5], lg[MAXN + 5]; void get_st() { for(int i=1;i<=dcnt;i++) { if( pf[dfn[i]] == hvy[dfn[i]] ) st[0][0][i] = g[dfn[i]] - dep[dfn[i]], st[1][0][i] = g[dfn[i]] + dep[dfn[i]]; else st[0][0][i] = f[dfn[i]] - dep[dfn[i]], st[1][0][i] = f[dfn[i]] + dep[dfn[i]]; } for(int j=1;j<20;j++) { int t = (1<<(j-1)); for(int i=1;i+t<=dcnt;i++) st[0][j][i] = max(st[0][j-1][i], st[0][j-1][i+t]), st[1][j][i] = max(st[1][j-1][i], st[1][j-1][i+t]); } for(int i=2;i<=dcnt;i++) lg[i] = lg[i>>1] + 1; } int rmq(int le, int ri, bool type) { if( le > ri ) return -INF; int k = lg[ri-le+1], l = (1<<k); return max(st[type][k][le], st[type][k][ri-l+1]); } int query(int u, int v, bool type) { int ret = -INF; while( top[u] != top[v] ) { ret = max(ret, rmq(tid[top[u]], tid[u]-1, type)); u = top[u]; if( pf[fa[u]] == u ) ret = max(ret, g[fa[u]] + (type ? 1 : -1)*dep[fa[u]]); else ret = max(ret, f[fa[u]] + (type ? 1 : -1)*dep[fa[u]]); u = fa[u]; } return max(ret, rmq(tid[v], tid[u]-1, type)); } int main() { int n, m; scanf("%d", &n); for(int i=1;i<n;i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); } dfs1(1, 0), dfs2(1, 1), dfs3(1), get_st(); scanf("%d", &m); for(int i=1;i<=m;i++) { int a, b; scanf("%d%d", &a, &b); if( dep[a] < dep[b] ) swap(a, b); int l = lca(a, b), dis = dep[a] + dep[b] - 2*dep[l]; int mid = get_fa(a, dep[a] - (dis - 1)/2), ans = max(f[a], dep[a] + query(a, mid, 0)); if( b == l ) ans = max(ans, max(dep[b] + query(b, 1, 0), -dep[b] + query(mid, b, 1))); else { int p = get_fa(a, dep[l] + 1), q = get_fa(b, dep[l] + 1); ans = max(ans, -dep[l] + query(mid, p, 1) + dep[b] - dep[l]); ans = max(ans, dep[b] + query(b, q, 0)); ans = max(ans, dep[b] + query(l, 1, 0)); ans = max(ans, f[b]); if( pf[l] == p ) { if( pg[l] == q ) ans = max(ans, dep[b] - dep[l] + h[l]); else ans = max(ans, dep[b] - dep[l] + g[l]); } else if( pf[l] == q ) { if( pg[l] == p ) ans = max(ans, dep[b] - dep[l] + h[l]); else ans = max(ans, dep[b] - dep[l] + g[l]); } else ans = max(ans, dep[b] - dep[l] + f[l]); } printf("%d\n", ans); } }

## @details@ ##

总之各种分类讨论还是非常令人心烦的。。。  
这个可能真的要写对拍，不然就得反复看自己有没有漏情况，或者是某种情况的公式推错了什么的。。。

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