题意：
给出一个n个点的树，有m个事件；
每次是将x到y的路径上所有点都投放一个z的物品；
求最后每个点上那个物品最多；
n，m<=100000；
题解：
一道数据结构好题；
首先这道题问的是最终答案，，那么把所有事件离线下来处理；
考虑如果树是一条链，那么对于这样一个序列问题怎么做？
将左端点x设置z数量加一，右端点y设为z数量-1；
然后用一个权值线段树去扫整个序列，查询最大值即为答案；
时间复杂度O((n+m)logm)，空间复杂度O(mlogm)；
十分优雅的做法，我们把它转移到树上；
树上的标记与序列大致相同，我们从叶节点向上扫整棵树；
那么在x,y结点标z数量加一，LCA(x,y)，fa(LCA(x,y))设置z数量-1；
这似乎是树链问题转化很常用的手段之一？
然后我们一样的向上扫。。。两个点扫到了一个根！
现在要把这两个线段树合并起来；
如果直接启发式合并复杂度有点奇怪吧，不过权值线段树有更加优越的方法；
直接递归合并！
如果两个树有一个没结点，直接返回有结点的那个；
如果都有结点就递归计算，然后将计算出来的新结点返回，两个旧结点回收；
这个的复杂度是总体是O(nlogn)的(单次可能O(n)但是总体卡不住)；
以下是PoPoQQQ大爷的精彩证明[鼓掌熊]：
我定义一棵线段树的势为节点个数
那么合并两棵线段树的代价为 两棵线段树的势和-新线段树的势
然后一开始所有线段树的势之和为O(nlogn)
一个线段树上有logn个节点
合并到最后有n个节点
所以最后的势能差是O(nlogn)
完事了
然后这题就能时间空间都是nlogn了
证明了复杂度可靠，那这题就置剩下实现的细节问题了；
别的倒是没什么，但是这题爆栈！爆栈！！！
然后改个宽搜就过了= =，真是够了；
代码：
#include<queue>#include<stdio.h>#include<string.h>#include<algorithm>#define N 110000#define MEM 2000000#define M 1000000000#define lson l,mid,ls[no]#define rson mid+1,r,rs[no]using namespace std;int fa[N][30],deep[N],size[N],ts[N],ans[N];int next[N<<2],kind[N<<2],head[N],ce;bool val[N<<2];int ma[MEM],kma[MEM],ls[MEM],rs[MEM],root[N],tot;int mp[MEM],top;queue<int>q;int newseg(){if(top)return mp[top–];return ++tot;}void delseg(int no){mp[++top]=no;ls[no]=0;rs[no]=0;ma[no]=0;}void Pushup(int no){if(ma[ls[no]]>=ma[rs[no]])ma[no]=ma[ls[no]],kma[no]=kma[ls[no]];elsema[no]=ma[rs[no]],kma[no]=kma[rs[no]];}void update(int l,int r,int &no,int k,int val){if(!no)no=newseg();if(l==r)ma[no]+=val,kma[no]=l;else{int mid=l+r>>1;if(k<=mid)update(lson,k,val);elseupdate(rson,k,val);Pushup(no);}}int merge(int l,int r,int nol,int nor){if(!nol||!nor)return nol+nor;int no=newseg();if(l==r){ma[no]=ma[nol]+ma[nor];kma[no]=l;}else{int mid=l+r>>1;ls[no]=merge(l,mid,ls[nol],ls[nor]);rs[no]=merge(mid+1,r,rs[nol],rs[nor]);Pushup(no);}delseg(nol),delseg(nor);return no;}namespace Graph{int to[N<<1],next[N<<1],head[N],ce;int tq[N],st,en;void add(int x,int y){to[++ce]=y;next[ce]=head[x];head[x]=ce;}void bfs(){tq[st=en=1]=1;int i,x;while(st<=en){x=tq[st++];size[x]=1,deep[x]=deep[fa[x][0]]+1;for(i=1;fa[x][i-1];i++)fa[x][i]=fa[fa[x][i-1]][i-1];for(i=head[x];i;i=next[i]){if(to[i]!=fa[x][0]){fa[to[i]][0]=x;tq[++en]=to[i];}}}while(en){size[fa[tq[en]][0]]+=size[tq[en]];if(size[tq[en]]==1)q.push(tq[en]);en–;}}};int LCA(int x,int y){if(deep[x]<deep[y])swap(x,y);int k=20;while(deep[x]!=deep[y]){if(deep[fa[x][k]]>=deep[y])x=fa[x][k];k–;}if(x==y)return x;k=20;while(k>=0){if(fa[x][k]!=fa[y][k])x=fa[x][k],y=fa[y][k];k–;}return fa[x][0];}void Insert(int x,int k,bool v){val[++ce]=v;kind[ce]=k;next[ce]=head[x];head[x]=ce;}int main(){int n,m,i,j,k,l,x,y,z;scanf("%d%d",&n,&m);for(i=1;i<n;i++){scanf("%d%d",&x,&y);Graph::add(x,y);Graph::add(y,x);}Graph::bfs();for(i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);l=LCA(x,y);Insert(x,z,1),Insert(y,z,1);Insert(l,z,0),Insert(fa[l][0],z,0);}while(!q.empty()){x=q.front(),q.pop();for(i=head[x];i;i=next[i])update(1,M,root[x],kind[i],val[i]?1:-1);ans[x]=kma[root[x]];root[fa[x][0]]=merge(1,M,root[x],root[fa[x][0]]);ts[fa[x][0]]+=size[x];if(ts[fa[x][0]]+1==size[fa[x][0]])q.push(fa[x][0]);}for(i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;}
可就是这样，还是有人，期望过多的温暖。
