1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
using A=array<array<ll,2>,8>;

int n,q;
vector<vector<pair<int,ll>>> g;
ll t[3],sm[8];

A dfs(int v,int p){
    A dp,nd,ch;
    for(int i=0;i<8;i++)dp[i]={-1,-1};
    dp[0][0]=0;
    for(auto [u,w]:g[v]){
        if(u==p)continue;
        ch=dfs(u,v);
        for(int i=0;i<8;i++)nd[i]={-1,-1};
        for(int m1=0;m1<8;m1++)for(int s1=0;s1<2;s1++){
            ll x=dp[m1][s1];
            if(x<0)continue;
            for(int m2=0;m2<8;m2++){
                if(m1&m2)continue;
                for(int s2=0;s2<2;s2++){
                    ll y0=ch[m2][s2];
                    if(y0<0)continue;
                    ll y=w+(s2?0:y0);
                    int bs=m1|m2;
                    int rm=7^bs;
                    for(int a=rm;;a=(a-1)&rm){
                        if(sm[a]<=x){
                            ll rx=x-sm[a];
                            int rm2=rm^a;
                            for(int b=rm2;;b=(b-1)&rm2){
                                if(sm[b]<=y){
                                    ll ry=y-sm[b];
                                    int m=bs|a|b;
                                    ll z=max({0LL,rx,ry});
                                    if(z>nd[m][s1])nd[m][s1]=z;
                                    if(!s1&&rx>0&&ry>0){
                                        for(int i=0;i<3;i++){
                                            if((m>>i)&1)continue;
                                            if(t[i]<=rx+ry&&0>nd[m|1<<i][1])nd[m|1<<i][1]=0;
                                        }
                                    }
                                }
                                if(!b)break;
                            }
                        }
                        if(!a)break;
                    }
                }
            }
        }
        dp=nd;
    }
    return dp;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>q;
    g.assign(n,{});
    for(int i=0;i<n-1;i++){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        --u;--v;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    while(q--){
        cin>>t[0]>>t[1]>>t[2];
        for(int m=0;m<8;m++){
            sm[m]=0;
            for(int i=0;i<3;i++)if((m>>i)&1)sm[m]+=t[i];
        }
        A r=dfs(0,-1);
        bool ok=0;
        for(int s=0;s<2;s++)for(int m=0;m<8;m++){
            ll x=r[m][s];
            if(x<0)continue;
            int rm=7^m;
            for(int a=rm;;a=(a-1)&rm){
                if(sm[a]<=x){
                    ok|=((m|a)==7);
                    if(ok)break;
                }
                if(!a)break;
            }
            if(ok)break;
        }
        cout<<(ok?"TAK\n":"NIE\n");
    }
    return 0;
}