题意：

给一棵$n$个节点的树和$m$条限制，每条限制形如$dis(x,ai)+dis(x,bi)≤di$，其中$dis(a,b)$表示$a$到$b$经过的边的个数。问图中是否存在$x$满足所有限制，有的话输出任意一个合法解，否则输出无解。 设$x$为根。 依次遍历每条限制，如果$𝑎𝑖,𝑏𝑖$均在$x$的子树中且限制不成立，那么$x$向这$2$个点的$lca$到$x$的这条链上向子树方向移动，直至满足限制，如果移动到$lca$处仍不满足限制则说明无解。

标程

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) std::cout<<a[i]<<' '; std::cout<<a[n]<<std::endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-1) std::cout<<a[i][j]<<' ';\
                        std::cout<<a[i][m]<<std::endl; \
                        } 
#define ALL(x) (x).begin(),(x).end()

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}

inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 

#define MAXN (310000)

int n,m;
int t_cnt=0,dfn[MAXN],dep[MAXN],r[MAXN];
ll deep[MAXN];

struct edge{
    int v,w;
};

std::vector<edge> e[MAXN];
int fa[MAXN][21];

void dfs(int x,int fa,ll d=0,ll d2=0) {
    ::fa[x][0]=fa;
    For(i,20) ::fa[x][i]=::fa[::fa[x][i-1]][i-1];
    deep[x]=d;dep[x]=d2;
    dfn[x]=++t_cnt;
    for(int i=0;i<SI(e[x]);i++) {
        edge node = e[x][i];
        if (node.v!=fa) {
            dfs(node.v,x,d+node.w,d2+1);
        }
    }
    r[x]=t_cnt;
}

int lca(int x,int y) {
    if (dep[x]<dep[y]) std::swap(x,y);
    RepD(i,20) if (dep[fa[x][i]]>=dep[y]) {
        x=fa[x][i];
    }
    RepD(i,20) if (fa[x][i]!=fa[y][i]) {
        x=fa[x][i],y=fa[y][i];
    }
    if (x!=y) x=fa[x][0],y=fa[y][0];
    return x;
}

ll dis(int x,int y) {
    return deep[x]+deep[y]-deep[lca(x,y)]*2;
}

int x[MAXN],y[MAXN],d[MAXN];

bool check(int root) {
    For(i,m) if (dis(x[i],root)+ dis(y[i],root)>d[i]) return 0; 
    return 1;
}

bool inside(int a,int b) {  
    return dfn[b]<=dfn[a] &&dfn[a]<=r[b] ;
}

int main()
{
//  freopen("bzoj4151.in","r",stdin);
    int t=read();
    while(t--) {
        std::cin>>n>>m;
        For(i,n) Rep(j,21) fa[i][j]=0;
        For(i,n) e[i].clear();
        For(i,n-1) {
            int u=read(),v=read(),w=1;
            e[u].pb({v,w});
            e[v].pb({u,w});
        }
        MEM(dfn)
        t_cnt=0;
        dfs(1,-1,0,1);
        int root=1;
        For(i,m) {
            x[i]=read(),y[i]=read(),d[i]=read();
            if (!(inside(x[i],root) && inside(y[i],root))) continue;
            while (dis(x[i],root) + dis(y[i],root)>d[i] && inside(x[i],root) &&inside(y[i],root) ) {
                bool fl=0;
                Rep(j,SI(e[root])) {
                    edge v=e[root][j];
                    if (inside(x[i],v.v) &&inside(y[i],v.v) && fa[v.v][0]==root ){
                        root=v.v;fl=1;break;
                    }
                }
                if (!fl) {
                    break;
                }
            }
        }
        if (check(root)) {
            printf("TAK %d\n",root);
        }
        else {
            puts("NIE");
        }
    }
    return 0;
}