hdu5029 Relief grain[树链剖分+离线标记]

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}.

题意

给出一棵 $n$个 节点的树,和 $m$次操作。 操作 $a$,$b$,$k$相当于将树上 $a,b$ 结点间的路径上的节点都加上一个 $type$ $k$,最后输出每个结点被加最多次的那个$type$, 若有多个 $type$ 被加的次数相同,输出编号最小的$type$ 的编号。

题解

把每次修改拆成 $<=log$ $n$ 条链,然后离线处理.

线段树存的是,目前各种标记有多少种,然后还有最大的出现次数

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
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e5+200;
int n,m,X,Y,Z;

int ne[maxn<<1],to[maxn<<1],po[maxn],id1;
inline void add(int x,int y) {id1++;to[id1]=y;ne[id1]=po[x];po[x]=id1;}

int son[maxn],fa[maxn],deep[maxn],sz[maxn];
inline void dfs1(int x)
{
son[x]=0;deep[x]=deep[fa[x]]+1;sz[x]=1;
for (int i=po[x];i;i=ne[i])
if (to[i]!=fa[x])
{
fa[to[i]]=x;
dfs1(to[i]);
sz[x]+=sz[to[i]];
if (sz[to[i]]>sz[son[x]]) son[x]=to[i];
}
}

int top[maxn],id[maxn],Map[maxn],dfs_time;
inline void dfs(int x,int last)
{
top[x]=last;id[x]=++dfs_time;Map[id[x]]=x;
if (son[x]==0) return;dfs(son[x],last);
for (int i=po[x];i;i=ne[i]) if (to[i]!=fa[x]&&to[i]!=son[x]) dfs(to[i],to[i]);
}

int t[maxn<<2],Max[maxn<<2],ans[maxn];
vector<int> G[maxn];
void work(int x,int y,int w)//拆询问
{
int tx=top[x],ty=top[y];
while (tx!=ty)
{
if (deep[tx]<deep[ty]) swap(tx,ty),swap(x,y);
G[id[tx]].push_back(w);
G[id[x]].push_back(-w);
x=fa[tx];tx=top[x];
}
if (id[x]>id[y]) swap(x,y);
G[id[x]].push_back(w);G[id[y]].push_back(-w);
}
void xg(int x,int y,int l,int r,int d)
{
if (l==r) {Max[d]=x;t[d]+=y;return;}
int mid=(l+r)>>1;
if (x<=mid) xg(x,y,l,mid,d<<1); else xg(x,y,mid+1,r,d<<1|1);
if (t[d<<1]>=t[d<<1|1]) Max[d]=Max[d<<1],t[d]=t[d<<1];
else Max[d]=Max[d<<1|1],t[d]=t[d<<1|1];
}
int maxcl;
int main()
{
while (scanf("%d",&n)!=EOF)
{
m=read();if (n==0&&m==0) return 0;
memset(ans,0,sizeof(ans));
id1=0;memset(po,0,sizeof(po));
for (int i=1;i<n;i++) {X=read();Y=read();add(X,Y);add(Y,X);}
dfs1(1);dfs_time=0;dfs(1,1);
memset(t,0,sizeof(t));memset(Max,0,sizeof(Max));
for (int i=1;i<=n;i++) G[i].clear();
//return 0;
maxcl=0;
for (int i=1;i<=m;i++) {X=read();Y=read();Z=read();work(X,Y,Z);qmax(maxcl,Z);}
for (int i=1;i<=n;i++)
{
for (int j=G[i].size()-1;j>=0;j--) if (G[i][j]>0) xg(G[i][j],1,1,maxcl,1);//打标记
ans[Map[i]]=Max[1];
if (t[1]==0) ans[Map[i]]=0;
for (int j=G[i].size()-1;j>=0;j--) if (G[i][j]<0) xg(-G[i][j],-1,1,maxcl,1);//删
}
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
return 0;
}