给你一棵树，现在有m个专家，每个专家计划从$a_i$走到$b_i$， 经过的距离不超过$d_i$，现在让你找一个点，使得所有专家的路途都能经过这个点

令$S_i$表示满足第i个专家的所有点，先检查1可不可以，不行的话，找到离根最远的专家i，找$S_i$中最靠近根的那个点

 

#include 
     
      using namespace std;#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)typedef pair
      
        P;const int N = 3e5 + 7;int n, m;vector
       
         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] + 1;    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, 1, n) g[i].clear();        rep(i, 1, n - 1) {            int x, y;            scanf("%d%d", &x, &y);            g[x].push_back(y);            g[y].push_back(x);                    }        rep(i, 1, 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 + 1) / 2;        };        auto solve = [&]() -> int {            dep[0] = -1;            dfs(1, 0);            int maxv = -1, t;            rep(i, 1, m) {                int d = calc(1, i);                if (d > maxv) {                    maxv = d; t = i;                }            }            if (maxv <= 0) return 1;            int u = req[t].a;            rep(i, 1, dep[req[t].a] - maxv) u = fa[u];            dfs(u, 0);            maxv = -1;            rep(i, 1, m) {                int d = calc(u, i);                if (d > maxv) maxv = d;            }            if (maxv <= 0) return u;            return -1;        };        int ans = solve();        if (ans < 0) printf("NIE\n");        else printf("TAK %d\n", ans);    }}/*2 5 3 1 2 2 3 2 43 5 1 4 2 5 5 53 2 1*/