ABC298Ex 题解
sunkuangzheng
·
·
题解
【题目大意】
**【题解】**
一遍过编译一遍过样例一遍 AC，写这题真的太舒服啦！！111
考虑我们把点分为两种类型：距离 $u$ 近和距离 $v$ 近。容易发现两部分各自构成连通块，且分界点是 $u,v$ 的路径中点，那么分开计算贡献。为了方便，以下令 $dep_u \ge dep_v,d = \operatorname{mid}(u,v),l = \operatorname{lca}(u,v)$。计算 $d,l$ 可以简单倍增完成。
$\operatorname{dis}(u,v) = dep_u+dep_v-2dep_{\operatorname{lca}(u,v)}$，显然前两部分可以直接算，最后一部分分类计算。 $T_d$ 指的是 $d$ 的子树。
- 距离 $u$ 更近的点都在 $d$ 的子树里，也即求 $\sum \limits_{v \in T_d} dep_{{\operatorname{lca}(u,v)}}$，枚举 $\operatorname{lca}(u,v)$，考虑有多少符合条件的 $v$，容易发现这个和式的值等于 $u \to d$ 的链上 $siz_u$ 的和，加上 $(dep_d-1)siz_u$。
- 距离 $v$ 更近的点都在 $d$ 的子树外。我们先计算 $\sum \limits_{i=1}^n dep_{\operatorname{lca}(u,i)}$，再减去 $i \in T_d$ 部分 $i$ 的贡献。第一部分的计算和上面一样，第二部分由于 $d$ 子树内任意点和 $v$ 的 $\operatorname{lca}$ 都是 $l$，所以贡献是 $-siz_d \cdot dep_{l}$。
据此计算即可。时间复杂度 $\mathcal O((n+q) \log n)$。
```cpp
/**
* author: sunkuangzheng
* created: 16.02.2024 20:17:27
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,fa[N][22],siz[N],dep[N],u,v,q; ll sm[N],sum; vector<int> g[N];
void dfs(int u,int f){
fa[u][0] = f,siz[u] = 1,dep[u] = dep[f] + 1,sum += dep[u];
for(int i = 1;i <= __lg(dep[u]);i ++) fa[u][i] = fa[fa[u][i-1]][i-1];
for(int v : g[u]) if(v != f) dfs(v,u),siz[u] += siz[v];
}void dfs2(int u,int f){sm[u] = sm[f] + siz[u]; for(int v : g[u]) if(v != f) dfs2(v,u);}
int lca(int u,int v){
if(dep[u] < dep[v]) swap(u,v);
while(dep[u] > dep[v]) u = fa[u][__lg(dep[u] - dep[v])];
for(int i = __lg(dep[u]);i >= 0;i --) if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
return (u == v ? u : fa[u][0]);
}int kfa(int u,int k){
for(int i = __lg(dep[u]);i >= 0;i --) if((k >> i) & 1) u = fa[u][i];
return u;
}int dis(int u,int v){return dep[u] + dep[v] - 2 * dep[lca(u,v)];}
void los(){
cin >> n;
for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
dfs(1,0),dfs2(1,0);
for(cin >> q;q --;){
if(cin >> u >> v,dep[u] < dep[v]) swap(u,v);
int di = dis(u,v),d = kfa(u,di / 2);
auto calc = [&](int u,int v){return sm[v] - sm[fa[u][0]];};
ll k = calc(d,u) + 1ll * siz[d] * (dep[d] - 1),p = calc(1,v) - 1ll * siz[d] * dep[lca(u,v)];
cout << 1ll * dep[u] * siz[d] + 1ll * dep[v] * (n - siz[d]) + sum - 2 * (k + p) << "\n";
}
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}
```