题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5029
题意：给你一个树，然后给你两点，将这两点之间的点涂上颜色，问涂色最多的那个颜色是什么，如果数量相同，就输出编号小的颜色
题解：树链剖分，这个题很巧妙，线段树维护的是一个颜色线段树，然后如果要涂[l,r]的颜色a，就在l处标记a +1，在r+1处标记a -1。然后从左往右依次更新线段树，并query，就能得出答案，我的跑了1400+ms,鸟神的非递归线段树只跑我一半的时间
详解请看：鸟神的这题题解：relief grain
1 #include<cstdio> 2 #include<cstring> 3 #define F(i,a,b) for(int i=a;i<=b;++i) 4 #define root 0,100001,1 5 #define ls l,m,rt<<1 6 #define rs m+1,r,rt<<1|1 7 #pragma comment(linker, "/STACK:102400000,102400000") 8 const int N=100010; 9 int n,m,x,y,z,idx,ans[N],sum[N*4],nxt[10*N],g[N],v[N*10],w[N*10],ed,pre[N],siz[N],dep[N],hson[N],top[N],tid[N],ftid[N]; 10 11 inline void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;} 12 //树链部分 13 void dfs1(int u,int fa){ 14 pre[u]=fa,siz[u]=1,dep[u]=dep[fa]+1,hson[u]=0; 15 for(int i=g[u];~i;i=nxt[i]){ 16 int vv=v[i]; 17 if(vv!=fa){ 18 dfs1(vv,u); 19 if(siz[vv]>siz[hson[u]])hson[u]=vv; 20 siz[u]+=siz[vv]; 21 } 22 } 23 } 24 25 void dfs2(int u,int tp){ 26 tid[u]=idx,ftid[idx++]=u,top[u]=tp; 27 if(hson[u])dfs2(hson[u],tp); 28 for(int i=g[u];~i;i=nxt[i]){ 29 int vv=v[i]; 30 if(vv!=pre[u]&&vv!=hson[u])dfs2(vv,vv); 31 } 32 } 33 34 void Update(int u,int v,int c){ 35 int fu=top[u],fv=top[v]; 36 while(fu!=fv){ 37 if(dep[fu]>=dep[fv]) 38 adg(tid[fu],c,1),adg(tid[u]+1,c,-1),u=pre[fu],fu=top[u]; 39 else adg(tid[fv],c,1),adg(tid[v]+1,c,-1),v=pre[fv],fv=top[v]; 40 } 41 if(dep[u]>dep[v])u=u^v,v=u^v,u=u^v; 42 adg(tid[u],c,1),adg(tid[v]+1,c,-1); 43 } 44 //线段树部分 45 void update(int x,int v,int l,int r,int rt){ 46 if(l==r){sum[rt]+=v;return;} 47 int m=(l+r)>>1; 48 if(x<=m)update(x,v,ls);else update(x,v,rs); 49 sum[rt]=sum[rt<<1]>sum[rt<<1|1]?sum[rt<<1]:sum[rt<<1|1]; 50 } 51 52 int query(int l,int r,int rt){ 53 if(l==r)return l; 54 int m=(l+r)>>1; 55 if(sum[rt]==sum[rt<<1])return query(ls); 56 else return query(rs); 57 } 58 59 int main(){ 60 while(~scanf("%d%d",&n,&m),n+m){ 61 memset(g,-1,sizeof(g)),ed=0; 62 F(i,1,n-1)scanf("%d%d",&x,&y),adg(x,y,0),adg(y,x,0); 63 dfs1(1,0),idx=1,dfs2(1,1); 64 F(i,0,4*N-1)sum[i]=0; 65 memset(g,-1,sizeof(g)),ed=0; 66 F(i,1,m)scanf("%d%d%d",&x,&y,&z),Update(x,y,z); 67 F(u,1,n){ 68 for(int i=g[u];~i;i=nxt[i])update(v[i],w[i],root); 69 ans[ftid[u]]=query(root); 70 } 71 F(i,1,n)printf("%d ",ans[i]); 72 } 73 return 0; 74 }