CF1783G 题解
namelessgugugu
·
·
题解
题面
给定一棵 n 个点，第 i 个点有点权 a_i 的树，对于一个点 u 定义偏心距 e(u) = \max\{ dis(u, v) + a_v\}，其中 dis(u, v) 表示两点在树上的距离。定义半径 r = \min\{e(u)\}。
$1 \leqslant n \leqslant 2 \times 10^5, 1 \leqslant m \leqslant 10^5$。
#### 题解
首先发现半径不是很好做，但是直径看上去就很有对称性，因此我们先考虑求直径的问题，也就是 $nd(u, v) = dis(u, v) + a_u + a_v, d = \max\{nd(x, y)\}$。
这个 $d$ 就相当于，在原树的基础上，每个点附带了两个长度为 $a_i$ 的链（这里挂两条的意义是要满足 $nd(u, u) = 2a_u$），得到的新树的直径，这种在一个正常的树上的直径往往能带来很多优秀的性质。
分析 $d$ 和 $r$ 之间的关系，考虑新树的直径中点，如果这个中点 $mid$ 在原树上，根据直径中点的性质有 $r = e(mid) = \lceil \frac{d}{2} \rceil$。否则我们就取不到这个 $mid$，那此时考虑这一条直径对应的原树上的路径 $(u, v)$，也就是 $d = nd(u, v)$，不妨设 $mid$ 在 $u$ 所对应的链上，则有 $e(u) = a_u$，而对于任何一个其他的点 $x$, 有 $e(x) \geqslant dis(x, u) + a_u > a_u = e(u)$，因此这种情况下 $r = e(u)$。另外我写完代码才发现第二种情况不可能发生，因为如果是这样会有 $d = nd(u, u)$。
通过刚才的分析，我们发现只要能维护新树的直径，以及这个直径对应的原树上的端点，我们就能轻松解决这个问题。
一个众所周知的结论是，如果用一条边将两棵树连接，则新直径端点一定都来源于旧的四个直径端点。实际上有一个更强的结论：在同一棵树上的两个虚树取并，新的直径端点同样来源于旧的四个直径端点。
简单证明一下，如果新直径端点都来源于旧的同一棵虚树，则结论显然成立。
如果来源于不同的虚树，那么假设新直径 $(u, v)$ 不满足上述结论，它们分别来自原虚树 $A$ 和 $B$。则路径 $(u, v)$ 一定是由一段来自于 $A$ 的路径与一段来自于 $B$ 的路径并起来的，不然图就不是树了。
此时考虑距离 $v$ 最远的在路径 $(u, v)$ 上且在虚树 $B$ 里面的点 $x$，那么原本虚树 $B$ 的两个直径端点 $a, b$ 一定有一个距离 $x$ 不少于 $v$ 到 $x$ 的距离，而且路径不会经过 $(u, x)$（这条路径完全不在 $B$ 里面）。$u$ 也可以以同样的方式调整。因此发现 $(u, v)$ 根本不是直径，出现矛盾，假设不成立。
有了这个结论，我们就可以以任意顺序合并每个点，并且需要存下来的信息量是非常少的，可以直接用线段树维护，一个节点存储编号在 $[l, r]$ 内的点（以及它们带着的链）组成的虚树的直径长度及其端点。
每一次合并需要 $O(1)$ 次求树上两点距离，这可以通过 $O(1)$ 或 $O(\log n)$ 的求 lca 来实现。
根据求 lca 方式的不同，最终复杂度是 $O(n \log n)$ 或者 $O(n \log^2 n)$，我这里使用的是 $O(n \log n) - O(1)$ 求 lca。
#### 代码
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
const int N = 200005;
int n, m, val[N];
struct Edge
{
int to, nxt;
} E[N << 1];
int head[N], tot;
inline void add(int f, int t)
{
E[++tot] = {t, head[f]}, head[f] = tot;
return;
}
int dep[N], dfn[N], tt, lg[N << 1], euler[N << 1], st[N << 1][20];
void dfs(int x, int from)
{
dep[x] = dep[from] + 1, euler[dfn[x] = ++tt] = x;
for (int i = head[x]; i;i = E[i].nxt)
{
int y = E[i].to;
if(y == from)
continue;
dfs(y, x), euler[++tt] = x;
}
return;
}
inline int depmin(int x, int y)
{
return dep[x] <= dep[y] ? x : y;
}
inline void st_init(void)
{
for (int i = 1; i <= tt;++i)
lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= tt;++i)
st[i][0] = euler[i];
for (int k = 1; k < lg[tt];++k)
for (int i = 1; i + (1 << k) - 1 <= tt;++i)
st[i][k] = depmin(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
return;
}
inline int query(int l, int r)
{
int k = lg[r - l + 1] - 1;
return depmin(st[l][k], st[r - (1 << k) + 1][k]);
}
inline int lca(int x, int y)
{
x = dfn[x], y = dfn[y];
if(x > y)
std::swap(x, y);
return query(x, y);
}
inline ll dis(int x, int y)
{
int f = lca(x, y);
return dep[x] + dep[y] - 2 * dep[f];
}
struct Info
{
int x, y;
ll len;
Info(void)
{
x = y = len = 0;
return;
}
Info(int _x, int _y)
{
x = _x, y = _y, len = dis(x, y) + val[x] + val[y];
return;
}
inline bool operator<(Info b) const
{
return len < b.len;
}
};
inline Info merge(Info a, Info b)
{
Info p[6] = {a, b, Info(a.x, b.x), Info(a.x, b.y), Info(a.y, b.x), Info(a.y, b.y)};
return *std::max_element(p, p + 6);
}
struct SgT
{
Info t[N << 2];
inline int ls(int x)
{
return x << 1;
}
inline int rs(int x)
{
return x << 1 | 1;
}
inline void pushup(int x)
{
t[x] = merge(t[ls(x)], t[rs(x)]);
return;
}
void build(int x, int l, int r)
{
if(l == r)
return t[x] = Info(l, l), void(0);
int mid = (l + r) >> 1;
build(ls(x), l, mid), build(rs(x), mid + 1, r);
pushup(x);
return;
}
void update(int x, int l, int r, int p)
{
if(l == r)
return t[x] = Info(p, p), void(0);
int mid = (l + r) >> 1;
if(p <= mid)
update(ls(x), l, mid, p);
else
update(rs(x), mid + 1, r, p);
pushup(x);
return;
}
inline ll query(void)
{
return std::max<ll>((t[1].len + 1) / 2, std::max(val[t[1].x], val[t[1].y]));
}
} T;
int main(void)
{
scanf("%d", &n);
for (int i = 1;i <= n;++i)
scanf("%d", val + i);
for (int i = 1, u, v; i < n;++i)
scanf("%d%d", &u, &v), add(u, v), add(v, u);
dfs(1, 0), st_init(), T.build(1, 1, n);
scanf("%d", &m);
for (int i = 1, x, y; i <= m;++i)
{
scanf("%d%d", &x, &y);
val[x] = y;
T.update(1, 1, n, x);
printf("%lld\n", T.query());
}
return 0;
}
```