Relief grain
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)
Total Submission(s): 686 Accepted Submission(s): 163
Problem Description The soil is cracking up because of the drought and the rabbit kingdom is facing a serious famine. The RRC(Rabbit Red Cross) organizes the distribution of relief grain in the disaster area.
We can regard the kingdom as a tree with n nodes and each node stands for a village. The distribution of the relief grain is divided into m phases. For each phases, the RRC will choose a path of the tree and distribute some relief grain of a certain type for every village located in the path.
There are many types of grains. The RRC wants to figure out which type of grain is distributed the most times in every village.
Input The input consists of at most 25 test cases.
For each test case, the first line contains two integer n and m indicating the number of villages and the number of phases.
The following n-1 lines describe the tree. Each of the lines contains two integer x and y indicating that there is an edge between the x-th village and the y-th village.
The following m lines describe the phases. Each line contains three integer x, y and z indicating that there is a distribution in the path from x-th village to y-th village with grain of type z. (1 <= n <= 100000, 0 <= m <= 100000, 1 <= x <= n, 1 <= y <= n, 1 <= z <= 100000)
The input ends by n = 0 and m = 0.
Output For each test case, output n integers. The i-th integer denotes the type that is distributed the most times in the i-th village. If there are multiple types which have the same times of distribution, output the minimal one. If there is no relief grain in a village, just output 0.
Sample Input
2 4
1 2
1 1 1
1 2 2
2 2 2
2 2 1
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
0 0
Sample Output
1
2
2
3
3
0
2
Hint
For the first test case, the relief grain in the 1st village is {1, 2}, and the relief grain in the 2nd village is {1, 2, 2}.
Source 2014 ACM/ICPC Asia Regional Guangzhou Online
Recommend hujie | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5037
解題思路：這道題想通的話很簡單，對數值建線段樹，由于是單點查詢，對于一個區間[l,r]置z來說，它的影響就是在l 位置把z的次數+1，然後在r+1的位置把z的次數-1，是以通過樹鍊剖分把區間拆成logn段，再把每段的左右點的z記錄下來，最後從左往右掃一遍，把這個點所有z的記錄都單點更新線段樹就行了，因為隻有mlogn段，是以總的插入的效率不會超過2m*logn*logn。 比賽時沒做出來真是too young too naive。。。
#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std;
int n,m;
vector<int> G[maxn],pl[maxn],pr[maxn];
int top[maxn],w[maxn],tw[maxn],pre[maxn],tn,son[maxn],dep[maxn],num[maxn],ans[maxn];
void init(){
for(int i=0;i<maxn;i++) G[i].clear(),pl[i].clear(),pr[i].clear();
tn=0;
dep[1]=0;
}
void dfs(int u,int fa){
pre[u]=fa,num[u]=1,son[u]=0;
int nn=G[u].size();
for(int i=0;i<nn;i++){
int v=G[u][i];
if(v!=fa){
dep[v]=dep[u]+1;
dfs(v,u);
num[u]+=num[v];
if(num[v]>num[son[u]]) son[u]=v;
}
}
}
void build_tree(int u,int fa){
w[u]=++tn,tw[tn]=u,top[u]=fa;
if(son[u]) build_tree(son[u],fa);
int nn=G[u].size();
for(int i=0;i<nn;i++){
int v=G[u][i];
if(v!=son[u]&&v!=pre[u]) build_tree(v,v);
}
}
void calc(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
pl[w[top[x]]].push_back(z);
pr[w[x]+1].push_back(z);
x=pre[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
pl[w[y]].push_back(z);
pr[w[x]+1].push_back(z);
}
struct tree{
int l,r;
int Max,v;
}a[maxn<<2];
void pushup(int k){
if(a[k<<1].Max>=a[k<<1|1].Max){
a[k].v=a[k<<1].v;
a[k].Max=a[k<<1].Max;
}else{
a[k].v=a[k<<1|1].v;
a[k].Max=a[k<<1|1].Max;
}
}
void build(int l,int r,int k){
a[k].l=l,a[k].r=r;
if(l==r){
a[k].v=l;
a[k].Max=0;
}else{
int mid=(l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
pushup(k);
}
}
void insert(int x,int v,int k){
if(a[k].l==a[k].r){
a[k].Max+=v;
}else{
int mid=(a[k].l+a[k].r)>>1;
if(x<=mid) insert(x,v,k<<1);
else insert(x,v,k<<1|1);
pushup(k);
}
}
void read(){
int u,v;
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
}
void solve(){
dfs(1,1);
build_tree(1,1);
int x,y,z;
for(int i=0;i<m;i++){
scanf("%d%d%d",&x,&y,&z);
calc(x,y,z);
}
build(1,100000,1);
for(int i=1;i<=n;i++){
for(int j=0;j<pl[i].size();j++) insert(pl[i][j],1,1);
for(int j=0;j<pr[i].size();j++) insert(pr[i][j],-1,1);
if(a[1].Max==0) ans[tw[i]]=0;
else ans[tw[i]]=a[1].v;
}
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
}
int main(){
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) break;
init();
read();
solve();
}
return 0;
}