「BZOJ3307」雨天的尾巴

题意：有一个 $N$ 个点的树，进行 $M$ 次操作，每次选择两个点 $x,y$，对从 $x$ 到 $y$ 的路径上所有的节点放置一个 $z$ 类型的标记。询问操作完成后，每个点存放最多的是哪种类型的标记。

这道题也要用到树上差分的思想，但是与上一道[POJ3417] Network不一样，这次是对所有的点标记，而不是边，这就是点差分。

点差分对于每个操作 $x,y$，来说，在 $x,y$ 点标记 $z$ 类型加 $1$，在 $LCA(x,y)$ 点标记 $z$ 类型减 $1$，在 $fa[LCA(x,y)]$ 点标记 $z$ 类型减 $1$(因为 $LCA(x,y)$ 也在路径上，所以只用减掉多算的那次，再把其父亲节点的标记减掉，以免影响到其他路径)。

但是由于类型过多，我们在统计子树和时，朴素方法肯定会超时，这时我们就可以采用线段树合并的方式来快速得到答案，对每个点 $x$，开一个动态开点的权值线段树，支持修改，维护最大值和最大值的位置，执行完操作后直接 $dfs$，合并线段树，得到子树和，进而得到答案。

由于要维护两个值，且题目要求输出的类型编号要最小，所以我们可以用 $pair$ 来存储线段树，$pair$ 在比较 $max$ 值时，先判断 $first$ 的大小，再判断 $second$，由于要编号最小，所以我们在维护编号时，取负值，最后在负回来就是最小。

本代码由于常数过大，被卡到了 $80$ 分，所以果断选择 $O_2$。

//luogu-O2
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int head[201010],cnt,tot;
int lc[6401010],rc[6401010];//左右儿子
int fa[201010][21],dep[201010];//lca倍增
int rt[201010],ans[201010];//根，答案
pair<int,int> maxx[6401010];//线段树维护最大值
struct node
{
	int next;
	int to;
}e[401010];
void add(int from,int to)
{
	e[++cnt].next=head[from];
	e[cnt].to=to;
	head[from]=cnt;
}
void dfs(int u)
{
	for(int i=1;i<=20;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa[u][0])
			continue;
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y)
		return y;
	for(int i=20;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
}
void pushup(int rt)
{
	maxx[rt]=max(maxx[lc[rt]],maxx[rc[rt]]);
}
void insert(int l,int r,int &rt,int pos,int val)//线段树
{
	if(!rt)
		rt=++tot;
	if(l==r)
	{
		maxx[rt]=make_pair(maxx[rt].first+val,-pos);
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
		insert(l,mid,lc[rt],pos,val);
	else
		insert(mid+1,r,rc[rt],pos,val);
	pushup(rt);
}
int merge(int l,int r,int x,int y)
{
	if(!x)
		return y;
	if(!y)
		return x;
	if(l==r)
	{
		maxx[x].first+=maxx[y].first;
		return x;
	}
	int mid=(l+r)>>1;
	lc[x]=merge(l,mid,lc[x],lc[y]);
	rc[x]=merge(mid+1,r,rc[x],rc[y]);
	pushup(x);
	return x;
}
void solve(int u)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v!=fa[u][0])
		{
			solve(v);
			rt[u]=merge(1,200000,rt[u],rt[v]);
		}
	}
	ans[u]=-maxx[rt[u]].second;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dep[1]=1;
	dfs(1);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		insert(1,200000,rt[a],c,1);
		insert(1,200000,rt[b],c,1);
		insert(1,200000,rt[lca(a,b)],c,-1);
		insert(1,200000,rt[fa[lca(a,b)][0]],c,-1);
	}
	solve(1);
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}