class Solution {
public int[] closestNode(int n, int[][] edges, int[][] query) {
//1.建图
Set<Integer>[] graph = new Set[n];
Arrays.setAll(graph,o->new HashSet<>());
for(int[] edge:edges){
int u = edge[0];
int v = edge[1];
graph[u].add(v);
graph[v].add(u);
}
//2.删边，定深
int[] depth = new int[n];
int[] parent = new int[n];
parent[0]=-1;
Arrays.fill(depth,-1);
depth[0]=0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
while(!queue.isEmpty()){
int node = queue.poll();
for(int next:graph[node]){
parent[next] = node;
depth[next]=depth[node]+1;
graph[next].remove(node);
queue.offer(next);
}
}
int m = query.length;
int[] ans = new int[m];
for(int i = 0; i < m; i++){
int[] q = query[i];
int a = q[0];
int b = q[1];
int c = q[2];
int d = getPublicParent(a,b,parent,depth);
int e = getPublicParent(a,c,parent,depth);
int f = getPublicParent(b,c,parent,depth);
int res = Math.min(depth[c]-depth[d],Math.min(depth[c]-depth[e],depth[c]-depth[f]));
int num = depth[c]-depth[d]==res?d:(depth[c]-depth[e] == res?e:f);
ans[i] = num;
}
return ans;
}
private int getPublicParent(int a, int b,int[] parent,int[] depth){
while(depth[a]>depth[b]) {
a = parent[a];
}
while(depth[b]>depth[a]){
b = parent[b];
}
while (a!=b){
a = parent[a];
b = parent[b];
}
return a;
}
}
class Solution {
public:
vector<int> closestNode(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
vector<vector<int>> g(n);
for (auto &it: edges) {
int u = it[0], v = it[1];
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector<vector<int>> fa(11, vector<int>(n, -1));
vector<int> dep(n, 1);
function<void(int, int)> dfs = [&](int u, int p) {
fa[0][u] = p;
if (p >= 0) dep[u] = dep[p] + 1;
for (auto v: g[u]) {
if (v != p) {
dfs(v, u);
}
}
};
dfs(0, -1);
for (int k = 0; k < 10; ++k) {
for (int i = 0; i < n; ++i) {
if (fa[k][i] >= 0) {
fa[k + 1][i] = fa[k][fa[k][i]];
}
}
}
function<int(int, int)> lca = [&](int a, int b) -> int {
if(dep[a] > dep[b])
swap(a, b);
while (dep[b] > dep[a])
b = fa[__lg(dep[b] - dep[a])][b];
if (a == b) return a;
for (int k = 10; k >= 0; --k) {
if (fa[k][a] != fa[k][b]) {
a = fa[k][a], b = fa[k][b];
}
}
return fa[0][a];
};
vector<int> ans(query.size());
for (int i = 0; i < query.size(); ++i) {
int u = query[i][0], v = query[i][1], t = query[i][2];
int uv = lca(u, v), ut = lca(u, t), vt = lca(v, t);
if (ut == uv) {
ans[i] = vt;
} else if (vt == uv) {
ans[i] = ut;
} else {
ans[i] = uv;
}
}
return ans;
}
};
class Solution:
def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
G = defaultdict(list)
for a,b in edges:
G[a].append(b)
G[b].append(a)
D = [[math.inf]*n for _ in range(n)]
for a in range(n):
que,D[a][a] = [a],0
while que:
tmp = []
for q in que:
for b in G[q]:
if D[a][b]!=math.inf: continue
D[a][b]=D[a][q]+1
tmp.append(b)
que = tmp
return [min(range(n), key=lambda x: D[x][a]+D[x][b]+D[x][q]) for a,b,q in query]
class Solution:
def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
def dfs(cur: int, pre: int, dep: int) -> None:
"""处理高度、父节点信息"""
depth[cur], parent[cur] = dep, pre
for next in adjMap[cur]:
if next == pre:
continue
dfs(next, cur, dep + 1)
def getPath(
root1: int, root2: int, level: DefaultDict[int, int], parent: DefaultDict[int, int]
) -> Set[int]:
"""求两个结点间的路径，不断上跳到LCA并记录经过的结点"""
res = {root1, root2}
if level[root1] < level[root2]:
root1, root2 = root2, root1
diff = level[root1] - level[root2]
for _ in range(diff):
root1 = parent[root1]
res |= {root1}
while root1 != root2:
root1 = parent[root1]
root2 = parent[root2]
res |= {root1, root2}
return res
def bfs(start: int, hit: Set[int]) -> int:
"""求到目标路径的最近交点"""
visited, queue = set([start]), deque([start])
while queue:
cur = queue.popleft()
if cur in hit:
return cur
for next in adjMap[cur]:
if next not in visited:
visited.add(next)
queue.append(next)
raise Exception("impossible")
adjMap = defaultdict(set)
for u, v in edges:
adjMap[u].add(v)
adjMap[v].add(u)
depth, parent = defaultdict(int), defaultdict(lambda: -1)
dfs(0, -1, 0)
return [bfs(root3, getPath(root1, root2, depth, parent)) for root1, root2, root3 in query]
