片 - 树上问题 - 1

MilkingAnAloe的博客客 / 2024-08-09 / 原文

欢迎来看 “片” （的简介）

由于-$看片$-生涯转瞬即逝，于是我选择对“$片$”进行一定的总结：

相信你一定看懂了

由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......

回到总部

点分治 $P4178$ $Tree$

解： 树的重心，树上$DFS$搜索，点分治

经过（两）天 (一) 夜的鏖战，总算 $\mathcal{TM}$ 的是把这个历史遗留问题解决了：

$——点分治——$

~~其实还有边分治~~

有挺多道题的，主要分享两道模板，废话，但只细讲一道

先从上面那道题开始。

暴力的想法就是往下找嘛吗，小小的加一个树上差分，估摸一下应该有个 $\mathcal{O}(n^3)$，~~卡卡不就过了~~，继续思考，~~看看题解~~，有一个初步的想法，一棵树，能长成个什么样子嘛，初步设想一个小 $\text{DP}$：

假设我们以 $1$ 为根，那么它一名伸出来的两点距离要么在其子树中，要么或这直接由 $1$ 引申出来，要么跨过 $1$，显然第二种讨论可以自己消化掉，即跨过 $1$ 的情况由两个由 $1$ 引申出来的情况来消化，若从这里开始思考，还会有一些问题，比如设有 $u$, $v$两个点的 $\text{LCA}$ 不等于 $1$ 那显然这个时候有多余的情况，怎么办？很简单，在往下递归的过程中记录这个子树的答案，然后在 $1$ 的答案里扣就可以了。

那么接下来考虑处理答案，首先将所有的权值进行排序，然后双指针秒了。

想一想排序 $\mathcal{O}(nlogn)$，再加一个根估计得有个 $\mathcal{O}(n^2logn)$，这基本就没什么用，排序等方面先不管，考虑这个根能不能进行一系列的优化，模式化的，就出现了重心，一个最大的子树大小一定不超过过 $\frac{sz}{2}$ 的抽象，这个时候，题解就会告诉你:

时间复杂的优化到了 $\mathcal{O}(nlog^2n)$

接下来的东西只针对于还是个 $\mathcal{SB}$ 的我：
why????
你肯定觉得每一个东西都会作为根，拼什么就优化了呢，实际上，这时从最开始就没有理解的表现，所谓的 $nlogn$, 实际是对于每一个子树的排序，就比如建一个有根树，我们排序所针对的并不是正一棵树，而是他的子节点。

例如红就会排绿和蓝，绿就会排蓝，所以实际上所谓的 $\mathcal{O}(n^2logn)$ 是一个及其保守党的估计，事实上最接近他的情况也只不过是当出现一整条链往下排的情况，然而再怎么保守，也会被可爱可敬的出题人发现，因此就有了这个神仙的优化：

重心

直接点说就是 $n^2logn$ 的其中一个 $n$ 代表的就是深度之类的东西。

由于加了重心之后最大的子树都只会有不到一半的大小那么这样递归下去，每一次大小都少一半，那么等到这棵树被我榨干了的时候就只需要 $logn$ 次，所以这个时间复杂度是 $\mathcal{O}(nlog^2n)$

嘿嘿嘿，就好了，注意每一层都要找重心哦。

然后就是实践，~~由于妈妈在催着睡觉，我就先直接放代码了~~

点击查看代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
#define endl '\n'
using namespace std;
const int MAXN=4e4+5;
ll n,Q;
struct edge{
	ll to,nxt,val;
};
edge e[MAXN<<1];
ll head[MAXN],tot=0;
void add_edge(ll u,ll v,ll w){
	++tot;
	e[tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[tot].val=w;
}
bool vis[MAXN];
ll sz[MAXN],wt[MAXN],rt=0,Tsz;
void GetRt(ll u,ll fath){//求重心，而且是每一棵子树
	sz[u]=1;
	wt[u]=0;
	for (int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if (v==fath || vis[v]) 
			continue;
		GetRt(v,u);
		sz[u]+=sz[v];
		wt[u]=max(wt[u],sz[v]);
	}
	wt[u]=max(wt[u],Tsz-sz[u]);
	if (wt[u]<wt[rt]) rt=u;
}
ll dis[MAXN];
void Getval(ll u,ll fath,ll vl){//寻找权值
	dis[++dis[0]]=vl;
	for (int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if (v==fath || vis[v]) continue;
		Getval(v,u,vl+e[i].val);
	}
}
ll m;
ll GetAns(ll u,ll vl){
	dis[0]=0;
	Getval(u,0,vl);
	sort(dis+1,dis+dis[0]+1);
	ll curans=0;
	for (int l=1,r=dis[0];r>=1 && l<=r;r--){
		while (dis[l]+dis[r]<=m && l<=r) curans+=r-l,++l;
	}
	return curans;
}
ll ans=0;
void dfs(ll u){
	vis[u]=1;
	ans+=GetAns(u,0);
	for (int i=head[u];i;i=e[i].nxt){
		ll v=e[i].to;
		if (vis[v]) continue;
		ans-=GetAns(v,e[i].val);
		Tsz=sz[v];
		wt[rt=0]=1145141919810ll;
		GetRt(v,0);
		dfs(rt);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(vis,0,sizeof(vis));
	cin>>n;
	for (int i=1;i<n;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	Tsz=n;
	wt[rt=0]=1145141919810ll;
	GetRt(1,0);
	cin>>m;
	dfs(rt);
	cout<<ans<<endl;
}

详细解说就算了，毕竟都是自己的代码，肯定是看得懂的，小小阐述一下，大致就是几个部分，找重心，在树上正常递归，以及算答案。

重心不用多赘述了。

树上的递归与算答案紧密相连，先是算一下 $u$ 自己本身的答案，这个时候的答案就是前面说的那个含有子节点路径重叠的点的贡献的答案，由 $u$ 算到每一个 $v$ 的时候，算一下 $v$ 的答案，并在最终答案中减去，这个部分就是去掉非法贡献，注意这个过程中只是一次普通的递归，不要想多了，然后在当前的子树中找到对应的重心，再以重心继续跑。

这样，你就学会了 点分治 了