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 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
| #include <bits/stdc++.h> #define MAXN 100005 #define MAXM 60 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r; int val,pos; }tree[MAXN*MAXM]; int tot; #define lc tree[i].l #define rc tree[i].r inline void pushup(int i){ if (tree[lc].val<tree[rc].val){ tree[i].val=tree[rc].val; tree[i].pos=tree[rc].pos; } else { tree[i].val=tree[lc].val; tree[i].pos=tree[lc].pos; } } void Update(int &i,int l,int r,int index,int val){ if (!i) i=++tot; if (l==r) { tree[i].val+=val; tree[i].pos=l; return ; } int mid=(l+r)>>1; if (index<=mid) Update(lc,l,mid,index,val); else Update(rc,mid+1,r,index,val); pushup(i); } int Merge(int x,int y,int l,int r){ if (!x||!y) return x+y; if (l==r){ tree[x].val+=tree[y].val; tree[x].pos=l; return x; } int mid=(l+r)>>1; tree[x].l=Merge(tree[x].l,tree[y].l,l,mid); tree[x].r=Merge(tree[x].r,tree[y].r,mid+1,r); pushup(x); return x; } } using namespace SegmentTree;
vector<int>G[MAXN]; inline void AddEdge(int u,int v){ G[u].push_back(v); } int anc[MAXN][MAXM],dep[MAXN],n,m; void dfs(int u,int father){ anc[u][0]=father; for (register int i=1;i<MAXM;++i){ anc[u][i]=anc[anc[u][i-1]][i-1]; } for (register int i=0;i<G[u].size();++i){ int v=G[u][i]; if (v!=father){ dep[v]=dep[u]+1; dfs(v,u); } } } inline int LCA(int u,int v){ if (dep[u]<dep[v]) swap(u,v); for (register int i=MAXM-1;i>=0;--i){ if (dep[anc[u][i]]>=dep[v]){ u=anc[u][i]; } } if (u==v) return u; for (register int i=MAXM-1;i>=0;--i){ if (anc[u][i]!=anc[v][i]){ u=anc[u][i]; v=anc[v][i]; } } return anc[u][0]; } inline void Init(){ memset(dep,0,sizeof(dep)); dfs(1,1); } int ans[MAXN],rt[MAXN]; void DP(int u,int father){ for (register int i=0;i<G[u].size();++i){ int v=G[u][i]; if (v!=father){ DP(v,u); rt[u]=Merge(rt[u],rt[v],1,MAXN-1); } } if (tree[rt[u]].val){ ans[u]=tree[rt[u]].pos; } } inline void Upd(int u,int pos,int val){ Update(rt[u],1,MAXN-1,pos,val); } inline void Add(int x,int y,int z){ int lca=LCA(x,y); Upd(x,z,1),Upd(y,z,1); Upd(lca,z,-1); if (lca!=1) Upd(anc[lca][0],z,-1); } int main(){ n=read(),m=read(); for (register int i=1;i<n;++i){ int u=read(),v=read(); AddEdge(u,v),AddEdge(v,u); } Init(); for (register int i=1;i<=m;++i){ int x=read(),y=read(),z=read(); Add(x,y,z); } DP(1,1); for (register int i=1;i<=n;++i){ printf("%d\n",ans[i]); } }
|