树的轻重链剖分。http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
剖分完了以后一条路径等同在O(logn)条连续的线段。
每次是区间修改，只要单点的最后结果，可以用部分和来维护。
对于各个点的回答，用以谷物为下标的线段树维护谷物的最值。
O(nlog^2n)
/********************************************************* * ------------------ * * author AbyssFish * **********************************************************/ #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<map> #include<set> #include<algorithm> #include<cmath> #include<numeric> #include<climits> using namespace std; const int maxn = 100000+5; int n, m; int hd[maxn], to[maxn*2], nx[maxn*2], ec; void add_edge(int u,int v) { to[ec] = v; nx[ec] = hd[u]; hd[u] = ec++; } void init_g(int n){ memset(hd+1,0xff,4*n); ec = 0; } #define eachedge int i = hd[u]; ~i; i = nx[i] #define ifvalid int v = to[i]; if(v == fa[u]) continue; /*-----------------------------------------------*/ int tr_sz[maxn]; int fa[maxn]; int dep[maxn]; int son[maxn]; int top[maxn]; int id[maxn];//0 base int id_cnt; //1 base indexed , node0 , size[0] = 0 void dfs(int u,int f = 0, int d = 0) { dep[u] = d; son[u] = 0; fa[u] = f; int &c = tr_sz[u]; c = 1; for(eachedge){ ifvalid dfs(v,u,d+1); c += tr_sz[v]; if(tr_sz[v] > tr_sz[son[u]]) son[u] = v; } } void sub_dv(int u,int tp) { top[u] = tp; id[u] = id_cnt++; if(son[u]) sub_dv(son[u],tp); for(eachedge){ ifvalid if(v == son[u]) continue; sub_dv(v,v); } } /*-----------------------------------------------*/ int maxz; #define para int o = 1, int l = 0, int r = maxz #define lo (o<<1) #define ro (o<<1|1) #define Tvar int md = (l+r)>>1; #define lsn lo,l,md #define rsn ro,md+1,r const int ST_SIZE = 1<<18; int fcnt[maxn]; int fid[ST_SIZE]; //单点最值的id //food indexed void build(para) { fid[o] = l; if(l < r){ Tvar build(lsn); build(rsn); } } inline void maintain(int o,int lc,int rc) { fid[o] = fcnt[fid[lc]] >= fcnt[fid[rc]] ? fid[lc] : fid[rc]; } void update(int z,int d,para) { if(l == r){ fcnt[z] += d; } else { Tvar if(z <= md) update(z,d,lsn); else update(z,d,rsn); maintain(o,lo,ro); } } /*-----------------------------------------------*/ void init() { init_g(n); for(int i = 1; i < n; i++){ int u,v; scanf("%d%d",&u,&v); add_edge(u,v); add_edge(v,u); } } vector<int> p_sum[maxn]; inline void add(int l,int r,int z) { p_sum[l].push_back(z); p_sum[r+1].push_back(-z); } inline void dump(int &h, int &v,int z) { add(id[h],id[v],z); v = fa[h]; h = top[v]; } int ans[maxn]; void solve() { id_cnt = 0; dfs(1); sub_dv(1,1); for(int i = 0; i <= id_cnt; i++) p_sum[i].clear(); maxz = 0; while(m--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); maxz = max(z,maxz); int a = top[x], b = top[y]; while(a != b){ dep[a] > dep[b] ? dump(a,x,z) : dump(b,y,z); } dep[x] < dep[y] ? add(id[x],id[y],z) : add(id[y],id[x],z); } memset(fcnt+1,0,4*maxz); build(); for(int i = 0; i < id_cnt; i++){ for(int j = 0; j < (int)p_sum[i].size(); j++){ int z = p_sum[i][j]; z > 0? update(z,1) : update(-z,-1); } ans[i] = fid[1]; } for(int i = 1; i <= n; i++){ printf("%d ",ans[id[i]]); } } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif //cout<<log2(maxn); while(scanf("%d%d",&n,&m),n+m){ init(); solve(); } return 0; }