题意：n个点构成的无根树，m次操作， 对于操作 x y z， 表示 x 到 y 路径上的 每个点 加一个 z 数字，可重复加。最后输出每个点 加的次数最多的那个数字，如果没有输出0.
赤裸裸的树链剖分，可是剖分之后 怎么用线段树维护每个点加的数字的次数呢。这里用到的思想类似于2014年上海网络赛的一道题。HDU5044，假如[x,y]这个区间上所有的点加上数字z，可以用两个标记 vec[x] + z,vec[y+1] -c。HDU上C++提交竟然爆栈，不过G++还是顺利ac了。具体见代码
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5+;
int siz[maxn],dep[maxn],son[maxn],fa[maxn];
struct
{
int to,next;
}e[maxn<<];
int tot,head[maxn];
void add_edge(int x,int y)
{
e[tot].to = y;
e[tot].next = head[x];
head[x] = tot++;
}
void dfs(int r)
{
son[r] = ;
siz[r] = ;
for (int i = head[r]; ~i; i = e[i].next)
{
int u = e[i].to;
if (fa[r] != u)
{
dep[u] = dep[r] + ;
fa[u] = r;
dfs(u);
if (siz[u] > siz[son[r]])
son[r] = u;
siz[r] += siz[u];
}
}
}
int top[maxn],pos[maxn],fp[maxn],idx;
void build(int r,int father)
{
pos[r] = ++idx; //记录每一个点 对应的位置
fp[pos[r]] = r; //记录每一个位置对应的点
top[r] = father;
if (son[r] > )
build(son[r],top[r]);
for (int i = head[r]; ~i; i = e[i].next)
{
if (fa[r] != e[i].to && son[r] != e[i].to)
build(e[i].to,e[i].to);
}
}
vector<int>vec[maxn];
void update(int x,int y,int v)
{
int fx = top[x];
int fy = top[y];
while (fx != fy)
{
if (dep[fx] < dep[fy])
{
swap(x,y),swap(fx,fy);
}
vec[pos[fx]].push_back(v); //有点类似于树状数组区间更新单点查询，
vec[pos[x] + ].push_back(-v);
x = fa[fx];
fx = top[x];
}
if (dep[x] > dep[y])
swap(x,y);
vec[pos[x]].push_back(v);
vec[pos[y] + ].push_back(-v);
} int n,m,seg[maxn<<],max_pos[maxn<<]; //max_pos为最大值在原始数组中的位置
void init()
{
int root = (+n)/;
idx = tot = ;
dep[root] = fa[root] = ;
memset(head,-,sizeof(head));
memset(siz,,sizeof(siz));
memset(seg,,sizeof(seg));
memset(max_pos,,sizeof(max_pos));
for (int i = ; i < n - ; i++)
{
int u,v;
scanf ("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(root);
build(root,root);
for (int i = ; i <= n; i++)
vec[i].clear();
for (int i = ; i < m; i++)
{
int x,y,v;
scanf ("%d%d%d",&x,&y,&v);
update(x,y,v);
}
}
void update(int l,int r,int pos,int x,int val)
{
if (l == r)
{
seg[pos] += val;
if (seg[pos] > )
max_pos[pos] = l;
else
max_pos[pos] = ;
return;
}
int mid = (l + r) >> ;
if (x <= mid)
update(l,mid,pos<<,x,val);
else
update(mid+,r,pos<<|,x,val);
if (seg[pos<<] >= seg[pos<<|])
{
seg[pos] = seg[pos<<];
max_pos[pos] = max_pos[pos<<];
}
else
{
seg[pos] = seg[pos<<|];
max_pos[pos] = max_pos[pos<<|];
}
}
int ans[maxn];
void solve()
{
for (int i = ; i <= n; i++)
{
for (unsigned int j = ; j < vec[i].size(); j++)
{
if (vec[i][j] > )
update(,maxn,,vec[i][j],);
else
update(,maxn,,-vec[i][j],-);
}
ans[fp[i]] = max_pos[];
}
for (int i = ; i <= n; i++)
printf("%d\n",ans[i]); }
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
while (~scanf ("%d%d",&n,&m))
{
if ((n == ) && (m == ))
break;
init();
solve();
}
return ;
}