C. 雨天的尾巴
题目描述
N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。
输入格式
第一行数字N，M
接下来N-1行，每行两个数字a,b,表示a与b间有一条边
再接下来M行，每行三个数字x,y,z.如题
输出格式
输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种，如果有
多种物品的数量一样，输出编号最小的。如果某个点没有物品则输出0
样例
样例输入
样例输出
数据范围与提示
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=10910^9109
暴力能得50分呢……
树上操作首先会想到树剖和树上差分吧，这里只说差分;
离线处理，权值线段树维护每一个点的状态（每种物品出现次数及其最大值），对于每次操作，将x+1，y+1，LCA（x，y）-1，fa[LCA]-1最后dfs合并线段树统计答案即可。
注意合并（修改）叶子节点时最大值是加而不是取max。
这道题比较恶心的是卡内存，卡了我四节课…
如果线段树合并操作是建新节点的话会MLE，代码如下：
int merge(int x,int y)
{
if(!x||!y)return x+y;
int now=++cnt;
sum(now)=sum(x)+sum(y);
l(now)=merge(l(x),l(y));
r(now)=merge(r(x),r(y));
if(!l(x) && !r(x))maxn(now)=maxn(x)+maxn(y);
else maxn(now)=max( maxn(l(now)) , maxn(r(now)) );
return now;
}
但是显然不这样的话数据会出错（将y的子树同时变为x的子树，之后在合并x时会修改数据），但是其实并不需要让线段树最后是正确的，只需要在y数据发生错误之前记录答案即可。
标程
#include<iostream>
#include<cstdio>
#include<map>
#include<time.h>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct edge
{
int u,v,next;
#define u(x) ed[x].u
#define v(x) ed[x].v
#define n(x) ed[x].next
}ed[];
int first[],num_e;
#define f(x) first[x]
int n,m,Q,fa[][],bin[],dep[];
int x[],y[],z[],z2[];
map<int,int> mp;
int mmp[];
int ans[]; struct tree
{
int l,r,sum,maxn;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum(x) tr[x].sum
#define maxn(x) tr[x].maxn
}tr[];
int cnt,rt[]; int ask(int l,int r,int a)
{
if(sum(a)==)return ;
if(l==r)return l;
int mid=(l+r)>>;
if(maxn(l(a))>=maxn(r(a)))return ask(l,mid,l(a));
return ask(mid+,r,r(a));
}
void add(int &mark,int l,int r,int loc,int val)
{
if(!mark)mark=++cnt;
if(l==r){sum(mark)+=val;maxn(mark)+=val;return;}
int mid=(l+r)>>;
if(loc<=mid)add(l(mark),l,mid,loc,val);
else add(r(mark),mid+,r,loc,val);
sum(mark)=sum(l(mark))+sum(r(mark));
maxn(mark)=max( maxn(l(mark)) , maxn(r(mark)));
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
l(x)=merge(l(x),l(y));
r(x)=merge(r(x),r(y));
sum(x)=sum(x)+sum(y);
if(!l(x) && !r(x))maxn(x)=maxn(x)+maxn(y);
else maxn(x)=max( maxn(l(x)) , maxn(r(x)) );
return x;
}
void dfs2(int x,int ffa);
inline int read();
int LCA(int x,int y);
void dfs(int x,int ffa);
inline void add_e(int u,int v);
signed main()
{
// freopen("4.in","r",stdin);
// freopen("out.txt","w",stdout); bin[]=;
for(int i=;i<=;i++)bin[i]=bin[i-]*;
n=read(),Q=read();
int ta,tb;
for(int i=;i<n;i++)
{
ta=read(),tb=read();
add_e(ta,tb);
add_e(tb,ta);
}
for(int j=;j<=Q;j++)
x[j]=read(),y[j]=read(),z[j]=read(),z2[j]=z[j];
sort(z2+,z2+Q+);
m=unique(z2+,z2+Q+)-z2-;
for(int i=;i<=Q;i++)
{
int loc=lower_bound(z2+,z2+m+,z[i])-z2;
mp[z[i]]=loc;
mmp[loc]=z[i];
}
dfs(,);
for(int j=;j<;j++)
for(int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
mmp[]=;
for(int i=;i<=Q;i++)
{
int loc=mp[z[i]],
lca=LCA(x[i],y[i]),
ffa=fa[lca][];
add(rt[x[i]],,m,loc,);
add(rt[y[i]],,m,loc,);
add(rt[lca], ,m,loc,-);
if(ffa)
add(rt[ffa] ,,m,loc,-);
}
dfs2(,);
ans[]=ask(,m,rt[]);
for(int i=;i<=n;i++)
printf("%d\n",mmp[ans[i]]);
}
void dfs2(int x,int ffa)
{
for(int i=f(x);i;i=n(i))
if(v(i)!=ffa)
{
dfs2(v(i),x);
ans[v(i)]=ask(,m,rt[v(i)]);
rt[x]=merge(rt[x],rt[v(i)]);
}
}
inline int read()
{
int s=;char a=getchar();
while(a<''||a>'')a=getchar();
while(a>=''&&a<=''){s=s*+a-'';a=getchar();}
return s;
}
inline void add_e(int u,int v)
{
++num_e;
u(num_e)=u;
v(num_e)=v;
n(num_e)=f(u);
f(u)=num_e;
}
void dfs(int x,int ffa)
{
fa[x][]=ffa;
dep[x]=dep[ffa]+;
for(int i=f(x);i;i=n(i))
if(v(i)!=ffa)
dfs(v(i),x);
}
int LCA(int x,int y)
{
if(dep[x]>dep[y])swap(x,y);
while(dep[x]!=dep[y])
for(int i=;;i++)
if(dep[fa[y][i]]<dep[x])
{
y=fa[y][i-];
break;
}
if(x==y)return x;
while(fa[x][]!=fa[y][])
for(int i=;;i++)
if(fa[x][i]==fa[y][i])
{x=fa[x][i-],y=fa[y][i-];break;}
return fa[x][];
}