2018-05-20 2 分钟读完 (大约 305 个字)

dsu on tree

可以用来解决一些有下列性质的问题：

对子树询问
没有修改

算法

算法步骤如下：

遍历的一个节点
- 递归所有的轻儿子
- 递归重儿子
- 统计轻儿子对答案的影响
- 计算答案
- 如果自己是轻儿子，消除影响

void add(int u, int father, int delta, int exc)
{
  //modify
  
	for (int i = head[u]; i; i = nextx[i])
	{
		int v = vet[i];
		if (v != father && v != exc)
		{
			add(v, u, delta, exc);
		}
	}
}

void solve(int u, int father, int cas)
{
	for (int i = head[u]; i; i = nextx[i])
	{
		int v = vet[i];
		if (v != father && v != son[u])
		{
			solve(v, u, 0);
		}
	}
	if (son[u])
	{
		solve(son[u], u, 1);
	}
	add(u, father, 1, son[u]);
  
  //calc ans
  
	if (cas == 0)
	{
		add(u, father, -1, 0);
    
    //clear
	}
}

时间复杂度

类似于树链剖分，可以证明对于一个点到根上的路径，轻边的边数是不会超过$logn$条的，因为经过一条轻边意味着子树大小至少乘$2$

那么根据算法，可以发现每个点需要消除影响的次数为$O(logn)$次，不需要消除影响的次数为$O(1)$次，那么总的时间复杂度为$O(nlogn)$

参考资料

# 树, 算法

dsu on tree

dsu on tree

算法

时间复杂度

参考资料

目录

标签云

归档

Your browser is out-of-date!