A and B and Lecture Rooms

題意要求我們找有多少個點$i$滿足$dis(i,x),dis(i,y)$，輸出點$i$的數量即可。

首先特判無解的情況就是$dis(x,y)$為奇數時，接下來我們討論有解的情況，大致分為兩類。

首先我們一定可以在$x?>y$的路徑上找到一個點滿足要求。

• 這個點不在$lca(x,y)$上：
  如圖我們要找的是(5, 6)的滿足要求的點有多少個，$lca(5,6)=7$
  顯然3是其路徑上的一個滿足要求的點，因為5號節點是從3號節點的父親連過來的，所以3號節點的父節點往上的節點均不滿足要求。
  同樣的6號節點是在3號節點的某一棵子樹上，所以3號節點要舍棄以4號節點為根節點的子樹，
  所以這種情況就變成了，$sz[3]?sz[4]$，顯然我們可以得到$x,y$路徑上的中點記為$u$，$x,y$中深度更大的節點$x$一定在$u$的子樹上，所以$u$的某個兒子$v$的子樹包含$x$節點要舍棄，
  所以答案就是$sz[u]?sz[v]$。

• 這個點在$lca(x,y)$上
  這個情況比上面就簡單了，$x,y$一定都在$lca$的某兩個不同的兒子上，
  所以找到包含$x$的兒子$u$，和包含$y$的兒子$v$，然后$n?sz[u]?sz[v]$即為答案。

最后特判一下$x==y$的情況即可。

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int head[N], to[N], nex[N], cnt = 1;int fa[N], top[N], son[N], sz[N], dep[N], id[N], rk[N], tot;int n, m;void add(int x, int y) {to[cnt] = y;nex[cnt] = head[x];head[x] = cnt++; }void dfs1(int rt, int f) {fa[rt] = f, dep[rt] = dep[f] + 1;sz[rt] = 1;for(int i = head[rt]; i; i = nex[i]) {if(to[i] == f) continue;dfs1(to[i], rt);sz[rt] += sz[to[i]];if(!son[rt] || sz[son[rt]] < sz[to[i]]) son[rt] = to[i];} }void dfs2(int rt, int tp) {top[rt] = tp;rk[++tot] = rt;id[rt] = tot;if(!son[rt]) return ;dfs2(son[rt], tp);for(int i = head[rt]; i; i = nex[i]) {if(to[i] == fa[rt] || to[i] == son[rt]) continue;dfs2(to[i], to[i]);} }int lca(int x, int y) {while(top[x] != top[y]) {if(dep[top[x]] < dep[top[y]]) swap(x, y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y; }int dis(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }int get_fa(int x, int k) {while(k > id[x] - id[top[x]]) {k -= id[x] - id[top[x]] + 1;x = fa[top[x]];}return rk[id[x] - k]; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d", &n);for(int i = 1; i < n; i++) {int x, y;scanf("%d %d", &x, &y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);scanf("%d", &m);for(int i = 1; i <= m; i++) {int x, y;scanf("%d %d", &x, &y);if(x == y) {printf("%d\n", n);continue;}int d = dis(x, y), l = lca(x, y);if(d & 1) {puts("0");continue;}if(dep[x] < dep[y]) swap(x, y);int p = get_fa(x, d / 2);if(p == l) {int u = get_fa(x, d / 2 - 1), v = get_fa(y, d / 2 - 1);printf("%d\n", n - sz[u] - sz[v]);}else {int u = get_fa(x, d / 2 - 1);printf("%d\n", sz[p] - sz[u]);}}return 0; }

總結

以上是生活随笔為你收集整理的A and B and Lecture Rooms的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。