L - Subway Lines Gym - 101908L [LCA+思维]

xiaoxiao2021-09-19  63

题意:给出一棵树,然后给出两个数对 ( a , b ) (a, b) (a,b), ( c , d ) (c, d) (c,d),询问在ab的最短路和cd的最短路重合了几个点。


题解:才开始想要标记路径但是LCA是倍增的不好弄,时间复杂度也太高,然后想了一下树上求最短路的知识,然后想到他们的LCA的高度,然后通过交叉走判断是否有重合的点。具体先选择LCA较小的点作为比较对象,然后另外两个点向当前两个点求LCA看高度与最低的LCA路径和,最后别忘了加上1(祖先)


a c c o d e : ac code: accode:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define met(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, a, b) for(int i = a; i >= b; i--) #define debug cout << "*" << endl; const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; const int DEG = 20; struct Edge { int to, next; } edge[maxn << 1]; int head[maxn], tot; void addEdge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void init() { tot = 0; met(head, -1); } int fa[maxn][DEG], deg[maxn]; void BFS(int root) { queue<int> que; deg[root] = 0; fa[root][0] = root; que.push(root); while(!que.empty()) { int tmp = que.front(); que.pop(); for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; for(int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; //cout << v << endl; if(v == fa[tmp][0]) continue; deg[v] = deg[tmp] + 1; fa[v][0] = tmp; que.push(v); } } } int LCA(int u, int v) { if(deg[u] > deg[v]) swap(u, v); int hu = deg[u], hv = deg[v]; int tu = u, tv = v; for(int det = hv - hu, i = 0; det; det >>= 1, i++) { if(det & 1) tv = fa[tv][i]; } if(tu == tv) return tu; for(int i = DEG - 1; i >= 0; i--) { if(fa[tu][i] == fa[tv][i]) { continue; } tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } bool flag[maxn]; int N, Q; int dis(int a, int b) { int f = LCA(a, b); return deg[a] + deg[b] - 2 * deg[f]; } int solve(int a, int b, int c, int d) { int lca = LCA(c, d); int t = LCA(a, b); if(deg[lca] < deg[t]) { lca = t; swap(a, c); swap(b, d); } t = LCA(a, c); int res = 0; int f = 0; if(deg[t] > deg[lca]) { res += dis(t, lca); } else if(deg[t] == deg[lca]) { f = 1; } t = LCA(a, d); if(deg[t] > deg[lca]) { res += dis(t, lca); } else if(deg[t] == deg[lca]) { f = 1; } t = LCA(b, c); if(deg[t] > deg[lca]) { res += dis(t, lca); } else if(deg[t] == deg[lca]) { f = 1; } t = LCA(b, d); if(deg[t] > deg[lca]) { res += dis(t, lca); } else if(deg[t] == deg[lca]) { f = 1; } res += f; return res; } int main() { int u, v, a, b, c, d; while(~scanf("%d%d", &N, &Q)) { init(); met(flag, false); rep(i, 2, N) scanf("%d%d", &u, &v), addEdge(u, v), addEdge(v, u), flag[v] = true; int root; for(int i = 1; i <= N; i++) { if(!flag[i]) { root = i; break; } } BFS(root); while(Q--) { scanf("%d%d%d%d", &a, &b, &c, &d); printf("%d\n", solve(a, b, c, d)); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-4823629.html

最新回复(0)