给你一棵树，现在有m个专家，每个专家计划从$a_i$走到$b_i$， 经过的距离不超过$d_i$，现在让你找一个点，使得所有专家的路途都能经过这个点
令$S_i$表示满足第i个专家的所有点，先检查1可不可以，不行的话，找到离根最远的专家i，找$S_i$中最靠近根的那个点
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
typedef pair<int, int> P;
const int N = 3e5 + ;
int n, m;
vector<int> g[N];
struct Requirement {
int a, b, d;
}req[N];
int fa[N], dep[N];
void dfs(int u, int f) {
dep[u] = dep[f] + ;
fa[u] = f;
for (int v: g[u])
if (v != f) dfs(v, u);
}
int main() {
int T;
scanf("%d", &T);
while (T --) {
scanf("%d%d", &n, &m);
rep(i, , n) g[i].clear();
rep(i, , n - ) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
rep(i, , m) {
scanf("%d%d%d", &req[i].a, &req[i].b, &req[i].d);
}
auto calc = [&](int v, int i) -> int {
return (dep[req[i].a] + dep[req[i].b] - req[i].d + ) / ;
};
auto solve = [&]() -> int {
dep[] = -;
dfs(, );
int maxv = -, t;
rep(i, , m) {
int d = calc(, i);
if (d > maxv) {
maxv = d; t = i;
}
}
if (maxv <= ) return ;
int u = req[t].a;
rep(i, , dep[req[t].a] - maxv) u = fa[u];
dfs(u, );
maxv = -;
rep(i, , m) {
int d = calc(u, i);
if (d > maxv) maxv = d;
}
if (maxv <= ) return u;
return -;
};
int ans = solve();
if (ans < ) printf("NIE\n");
else printf("TAK %d\n", ans);
}
}
/*
2
5 3
1 2
2 3
2 4
3 5
1 4 2
5 5 5
3 2 1
*/