XV Open Cup named after E.V. Pankratiev. GP of Central Europe (AMPPZ-2014)--J.Cave

#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 + 7;
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] + 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 4
3 5 
1 4 2 
5 5 5
3 2 1
*/