雨天的尾巴（P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并）

1.题意简化

N个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。

2.思路

• 首先这道题肯定要用先建树，然后我们可以在树上的每个节点建一个权值线段树，考虑到空间问题（每个点都有1个权值为1e9的树），我们采用动态开点，在求解答案时我们再合并线段树

• 对于x到y的路径上发放物品可以转化为4个步骤：
  1.从x到根节点发放1次物品
  2.从y到根节点发放1次物品
  3.设lca=x，y的最近公共祖先，我们从lca到根节点撤回1次物品
  4.从lca的父节点到根节点撤回1次物品、
  （可以自己手推一下）

• 对于权值线段树上的每个节点结构体中存储4个数据左儿子编号，右儿子编号，该区间最多物品的编号（w），该区间最多物品的数量（num）（也可以不用结构体，单独开数组存），在每次合并时比较两区间num大小，并更改，
  最终每个点的答案就是其所对应权值线段树根节点的w

• 发放物品：每次发放的4个操作分别只在权值线段树上update一次（这样我们每次合并后其父节点相当于都是也update过了的），求答案是从上往下dfs递归去求，如：

void dfs2(int x)
{
	for (int i=he[x];i;i=ne[i])
	  if (to[i]!=f[x][0])
	  {
	  	dfs2(to[i]);
	  	root[x]=merge(root[x],root[to[i]],1,maxn);
	  }
	if (tree[root[x]].num)
	  ans[x]=tree[root[x]].w;
}

3.注意

• 空间问题：m为动态开点的次数，每次插入新增log（n）个节点，n为值域
  我们每次发放物品对应4个操作所以权值线段树的空间可以开1e5*80

• 这里是swap（x，y）不是（d[x],d[y])：

	if (d[x]>d[y]) swap(x,y);

• 权值线段树叶子节点(l==r),l就为该点的w：

	if (l==r) 
	{
		tree[rt].w=l;
		tree[rt].num+=val;
		return;
	}

• 在权值线段树上左区间的值域肯定要小于右区间，这样就不用再比较w的大小了：

void pushup(int rt)
{
	if (tree[lson].num>=tree[rson].num)
	{
		tree[rt].num=tree[lson].num;
		tree[rt].w=tree[lson].w;
		return;
	 } 
	else
	{
		tree[rt].num=tree[rson].num;
		tree[rt].w=tree[rson].w;
		return;
	}
}

• 由于加减的问题可能会出现w不为0，但num为0的情况，所以要加一个判断：

	if (tree[root[x]].num)
	  ans[x]=tree[root[x]].w;

最后就是完整代码啦（开心）：

#include<bits/stdc++.h>
#define lson tree[rt].ls
#define rson tree[rt].rs
using namespace std;
const int maxn=1e5+10;
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
struct node{
	int ls,rs;
	int num;//num为最大物品的数量
	int w;//w为最大物品的编号 
}tree[maxn*80];
int d[maxn],f[maxn][30];//lca需要的数组，d表示深度，f为倍增 
int he[maxn],ne[maxn*2],to[maxn*2],tot;//链式前向星存图 
int ans[maxn],root[maxn];//ans存答案，root记录根节点 
int n,m,tmp;
void addedge(int u,int v)
{
	ne[++tot]=he[u];
	he[u]=tot;
	to[tot]=v;
}
bool v[maxn];
void dfs1(int x,int fa)//为lca做预处理操作 
{
	v[x]=1;
	d[x]=d[fa]+1;
	for (int j=1;(1<<j)<=n;j++)
	  f[x][j]=f[f[x][j-1]][j-1];
	for (int i=he[x];i;i=ne[i])
	  if (!v[to[i]]) 
	    {
	    	f[to[i]][0]=x;
	    	dfs1(to[i],x);
	    }
}
int lca(int x,int y)//求最近公共祖先 
{
	if (d[x]>d[y]) swap(x,y);
	int k=log2(d[y]);
	for (int j=k;j>=0;j--)
	  if (d[f[y][j]]>=d[x]) 
	    y=f[y][j];
	if (x==y) return x;
	k=log2(d[y]);
	for (int j=k;j>=0;j--)
	  if (f[x][j]!=f[y][j]) 
	  {
	  	x=f[x][j];
	  	y=f[y][j];
	  }
	return f[x][0];
}
void pushup(int rt)
{
	if (tree[lson].num>=tree[rson].num)
	{
		tree[rt].num=tree[lson].num;
		tree[rt].w=tree[lson].w;
		return;
	 } 
	else
	{
		tree[rt].num=tree[rson].num;
		tree[rt].w=tree[rson].w;
		return;
	}
}
void update(int &rt,int l,int r,int pos,int val)//更新操作 
{
	if (!rt) rt=++tmp;
	if (l==r) 
	{
		tree[rt].w=l;
		tree[rt].num+=val;
		return;
	}
	int mid=(l+r)>>1;
	if (pos<=mid) update(lson,l,mid,pos,val);
	else update(rson,mid+1,r,pos,val);
	pushup(rt);
}
int merge(int ra,int rb,int l,int r)//合并操作 
{
	if (!ra||!rb) return ra|rb;
	if (l==r) 
	{
		tree[ra].num+=tree[rb].num;
		return ra;
	}
	int mid=(l+r)>>1;
	tree[ra].ls=merge(tree[ra].ls,tree[rb].ls,l,mid);
	tree[ra].rs=merge(tree[ra].rs,tree[rb].rs,mid+1,r);
	pushup(ra);
	return ra;
}
void dfs2(int x)//合并权值线段树，求解答案 
{
	for (int i=he[x];i;i=ne[i])
	  if (to[i]!=f[x][0])
	  {
	  	dfs2(to[i]);
	  	root[x]=merge(root[x],root[to[i]],1,maxn);
	  }
	if (tree[root[x]].num)
	  ans[x]=tree[root[x]].w;
}
int main()
{
	n=read();
	m=read();
	for (int i=1,a,b;i<n;i++) 
	{
		a=read();
		b=read();
		addedge(a,b);
		addedge(b,a); 
	}
	dfs1(1,0);
	for (int i=1,x,y,p;i<=m;i++)
	{
		x=read();
		y=read();
		p=read();
		int t=lca(x,y); 
		update(root[x],1,maxn,p,1);//从 x 到 根节点 发放1次物品 
		update(root[y],1,maxn,p,1);//从 y 到 根节点 发放1次物品
		update(root[t],1,maxn,p,-1);//从 lca 到 根节点 撤回1次物品
		update(root[f[t][0]],1,maxn,p,-1);//从 lca的父节点 到 根节点 撤回1次物品
	}
	dfs2(1);
	for (int i=1;i<=n;i++)
	  printf("%d\n",ans[i]);
	return 0;
 } 

完结撒花！o(￣▽￣)ブ