1 #include <cstdio>  2 #include <vector>  3 #include <cstdlib>  4 #include <cstring>  5 #include <algorithm>  6 using namespace std;  7 const int maxn = 1e5+10;  8 int siz[maxn],dep[maxn],son[maxn],fa[maxn];  9 struct 10 { 11     int to,next; 12 }e[maxn<<1]; 13 int tot,head[maxn]; 14 void add_edge(int x,int y) 15 { 16     e[tot].to = y; 17     e[tot].next = head[x]; 18     head[x] = tot++; 19 } 20 void dfs(int r) 21 { 22     son[r] = 0; 23     siz[r] = 1; 24     for (int i = head[r]; ~i; i = e[i].next) 25     { 26         int u = e[i].to; 27         if (fa[r] != u) 28         { 29             dep[u] = dep[r] + 1; 30             fa[u] = r; 31             dfs(u); 32             if (siz[u] > siz[son[r]]) 33                 son[r] = u; 34             siz[r] += siz[u]; 35         } 36     } 37 } 38 int top[maxn],pos[maxn],fp[maxn],idx; 39 void build(int r,int father) 40 { 41     pos[r] = ++idx;                           //记录每一个点 对应的位置 42     fp[pos[r]] = r;                          //记录每一个位置对应的点 43     top[r] = father; 44     if (son[r] > 0) 45         build(son[r],top[r]); 46     for (int i = head[r]; ~i; i = e[i].next) 47     { 48         if (fa[r] != e[i].to && son[r] != e[i].to) 49             build(e[i].to,e[i].to); 50     } 51 } 52 vector<int>vec[maxn]; 53 void update(int x,int y,int v) 54 { 55     int fx = top[x]; 56     int fy = top[y]; 57     while (fx != fy) 58     { 59         if (dep[fx] < dep[fy]) 60         { 61             swap(x,y),swap(fx,fy); 62         } 63         vec[pos[fx]].push_back(v);                       //有点类似于树状数组区间更新单点查询， 64         vec[pos[x] + 1].push_back(-v); 65         x = fa[fx]; 66         fx = top[x]; 67     } 68     if (dep[x] > dep[y]) 69         swap(x,y); 70     vec[pos[x]].push_back(v); 71     vec[pos[y] + 1].push_back(-v); 72 } 73  74 int n,m,seg[maxn<<2],max_pos[maxn<<2];         //max_pos为最大值在原始数组中的位置 75 void init() 76 { 77     int root = (1+n)/2; 78     idx = tot = 0; 79     dep[root] = fa[root] = 0; 80     memset(head,-1,sizeof(head)); 81     memset(siz,0,sizeof(siz)); 82     memset(seg,0,sizeof(seg)); 83     memset(max_pos,0,sizeof(max_pos)); 84     for (int i = 0; i < n - 1; i++) 85     { 86         int u,v; 87         scanf ("%d%d",&u,&v); 88         add_edge(u,v); 89         add_edge(v,u); 90     } 91     dfs(root); 92     build(root,root); 93     for (int i = 1; i <= n; i++) 94         vec[i].clear(); 95     for (int i = 0; i < m; i++) 96     { 97         int x,y,v; 98         scanf ("%d%d%d",&x,&y,&v); 99         update(x,y,v);100     }101 }102 void update(int l,int r,int pos,int x,int val)103 {104     if (l == r)105     {106         seg[pos] += val;107         if (seg[pos] > 0)108             max_pos[pos] = l;109         else110             max_pos[pos] = 0;111         return;112     }113     int mid = (l + r) >> 1;114     if (x <= mid)115         update(l,mid,pos<<1,x,val);116     else117         update(mid+1,r,pos<<1|1,x,val);118     if (seg[pos<<1] >= seg[pos<<1|1])119     {120         seg[pos] = seg[pos<<1];121         max_pos[pos] = max_pos[pos<<1];122     }123     else124     {125         seg[pos] = seg[pos<<1|1];126         max_pos[pos] = max_pos[pos<<1|1];127     }128 }129 int ans[maxn];130 void solve()131 {132     for (int i = 1; i <= n; i++)133     {134         for (unsigned int j = 0; j < vec[i].size(); j++)135         {136             if (vec[i][j] > 0)137                 update(1,maxn,1,vec[i][j],1);138             else139                 update(1,maxn,1,-vec[i][j],-1);140         }141         ans[fp[i]] = max_pos[1];142     }143     for (int i = 1; i <= n; i++)144         printf("%d\n",ans[i]);145 146 }147 int main(void)148 {149     #ifndef ONLINE_JUDGE150         freopen("in.txt","r",stdin);151     #endif152     while (~scanf ("%d%d",&n,&m))153     {154         if ((n == 0) && (m == 0))155             break;156         init();157         solve();158     }159     return 0;160 }