算法

点分治用于处理大规模的树上路径。算法大致过程是对于一棵树，以其重心为根，先维护经过根的路径贡献的答案，再删去重心得到若干子树，对这些子树重复上述过程。复杂度为 $O(N\log N)$ （选重心进行分治的话可以达到 $\log N$ 层，每层复杂度总和为 $O(N)$ ）。

例题

洛谷 P3806 【模板】点分治1

P3806 【模板】点分治1

代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
#define bl(u,i) for(int i=head[u];i;i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read() {}
void OP() {}
void op() {}
template <typename T, typename... T2>
inline void read(T &_, T2 &... oth)
{
    int __=0;
    _=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            __=1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        _=_*10+ch-48;
        ch=getchar();
    }
    _=__?-_:_;
    read(oth...);
}
template <typename T>
void Out(T _)
{
    if(_<0)
    {
        putchar('-');
        _=-_;
    }
    if(_>=10)
       Out(_/10);
    putchar(_%10+'0');
}
template <typename T, typename... T2>
inline void OP(T _, T2... oth)
{
	Out(_);
	putchar('\n');
	OP(oth...);
}
template <typename T, typename... T2>
inline void op(T _, T2... oth)
{
	Out(_);
	putchar(' ');
	op(oth...);
}
/*#################################*/
const ll N=1E4+10,M=105,K=1E7+10;
ll n,q,rt,sum,top,tot;
ll siz[N],maxp[N],dis[N],Q[M],rec[N],head[N];
bool del[N],exist[K],ans[M];
struct Edge{
	ll nxt,to,w;
}e[N<<1];
void add_edge(ll u,ll v,ll w,int flag)
{
	e[++tot]=(Edge){head[u],v,w};
	head[u]=tot;
	if(flag)
		add_edge(v,u,w,0);
}
void gert(ll u,ll fa)
{
	siz[u]=1;
	maxp[u]=0;
	bl(u,i)
	{
		ll v=e[i].to;
		if(del[v] || v==fa)
			continue;
		gert(v,u);
		siz[u]+=siz[v];
		maxp[u]=max(maxp[u],siz[v]);
	}
	maxp[u]=max(maxp[u],sum-siz[u]);
	if(maxp[u]<maxp[rt])
		rt=u;
}
void getdis(ll u,ll fa)
{
	rec[++top]=dis[u];
	bl(u,i)
	{
		ll v=e[i].to;
		if(v==fa || del[v])
			continue;
		dis[v]=dis[u]+e[i].w;
		getdis(v,u);
	}
}
void solve(ll u)
{
	vector<ll> ve;
	bl(u,i)
	{
		ll v=e[i].to;
		if(del[v])
			continue;
		top=0;
		dis[v]=e[i].w;
		getdis(v,u);
		rep(i,1,top)
			rep(question,1,q)
				if(Q[question]>=rec[i])
					ans[question]|=exist[Q[question]-rec[i]];
		rep(i,1,top)
		{
			if(rec[i]>1e7)
				continue;
			exist[rec[i]]=true;
			ve.emplace_back(rec[i]);
		}
	}
	for(auto k:ve)
		exist[k]=false;
}
void divide(ll u)
{
	del[u]=exist[0]=true;
	solve(u);
	bl(u,i)
	{
		ll v=e[i].to;
		if(del[v])
			continue;
		maxp[rt=0]=sum=siz[v];
		gert(v,0);
		gert(rt,0);
		divide(rt);
	}
}
int main()
{
	read(n,q);
	ll u,v,w;
	rep(i,1,n-1)
	{
		read(u,v,w);
		add_edge(u,v,w,1);
	}
	rep(i,1,q)
		read(Q[i]);
	maxp[0]=sum=n;
	gert(1,0);
	gert(rt,0);
	divide(rt);
	rep(i,1,q)
		puts(ans[i]?"AYE":"NAY");
}
复制代码

Codeforces VK Cup 2012 Round 1 D. Distance in Tree

思路

点分治裸题。另外还可以用树形DP来做，设 $f[u][i]$ 为与 $u$ 点距离为 $i$ 的点个数，每次维护某个结点 $v$ 对 $u$ 的贡献之前，先计算它对答案的贡献，这样就不会出现往返的路径。

点分治代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
#define bl(u,i) for(int i=head[u];i;i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read() {}
void OP() {}
void op() {}
template <typename T, typename... T2>
inline void read(T &_, T2 &... oth)
{
    int __=0;
    _=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            __=1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        _=_*10+ch-48;
        ch=getchar();
    }
    _=__?-_:_;
    read(oth...);
}
template <typename T>
void Out(T _)
{
    if(_<0)
    {
        putchar('-');
        _=-_;
    }
    if(_>=10)
       Out(_/10);
    putchar(_%10+'0');
}
template <typename T, typename... T2>
inline void OP(T _, T2... oth)
{
	Out(_);
	putchar('\n');
	OP(oth...);
}
template <typename T, typename... T2>
inline void op(T _, T2... oth)
{
	Out(_);
	putchar(' ');
	op(oth...);
}
/*#################################*/
const ll N=5E4+10;
ll n,k,sum,rt,tot,ans,top;
ll head[N],maxp[N],siz[N],exist[N],rec[N],dis[N];
bool del[N];
struct Edge{
	ll nxt,to,w;
}e[N<<1];
void add_edge(ll u,ll v,ll w,int flag)
{
	e[++tot]=(Edge){head[u],v,w};
	head[u]=tot;
	if(flag)
		add_edge(v,u,w,0);
}
void gert(ll u,ll fa)
{
	siz[u]=1;
	maxp[u]=0;
	bl(u,i)
	{
		ll v=e[i].to;
		if(v==fa || del[v])
			continue;
		gert(v,u);
		siz[u]+=siz[v];
		maxp[u]=max(maxp[u],siz[v]);
	}
	maxp[u]=max(maxp[u],sum-siz[u]);
	if(maxp[u]<maxp[rt])
		rt=u;
}
void getdis(ll u,ll fa)
{
	rec[++top]=dis[u];
	bl(u,i)
	{
		ll v=e[i].to;
		if(v==fa || del[v])
			continue;
		dis[v]=dis[u]+1;
		getdis(v,u);
	}
}
void solve(ll u)
{
	vector<ll> ve;
	bl(u,i)
	{
		ll v=e[i].to;
		if(del[v])
			continue;
		dis[v]=1;
		top=0;
		getdis(v,u);
		rep(i,1,top)
			if(rec[i]<=k)
				ans+=exist[k-rec[i]];
		rep(i,1,top)
		{
			ve.emplace_back(rec[i]);
			exist[rec[i]]++;
		}
	}
	for(auto num:ve)
		exist[num]--;
}
void divide(ll u)
{
	del[u]=true;
	exist[0]=1;
	solve(u);
	bl(u,i)
	{
		ll v=e[i].to;
		if(del[v])
			continue;
		maxp[rt=0]=sum=siz[v];
		gert(v,0);
		gert(rt,0);
		divide(rt);
	}
}
int main()
{
	read(n,k);
	ll u,v;
	rep(i,1,n-1)
	{
		read(u,v);
		add_edge(u,v,1,1);
	}
	maxp[0]=sum=n;
	gert(1,0);
	gert(rt,0);
	divide(rt);
	OP(ans);
}
复制代码

树形DP代码

#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
#define bl(u,i) for(int i=head[u];i;i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll> 
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read() {}
void OP() {}
void op() {}
template <typename T, typename... T2>
inline void read(T &_, T2 &... oth)
{
    int __=0;
    _=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            __=1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        _=_*10+ch-48;
        ch=getchar();
    }
    _=__?-_:_;
    read(oth...);
}
template <typename T>
void Out(T _)
{
    if(_<0)
    {
        putchar('-');
        _=-_;
    }
    if(_>=10)
       Out(_/10);
    putchar(_%10+'0');
}
template <typename T, typename... T2>
inline void OP(T _, T2... oth)
{
	Out(_);
	putchar('\n');
	OP(oth...);
}
template <typename T, typename... T2>
inline void op(T _, T2... oth)
{
	Out(_);
	putchar(' ');
	op(oth...);
}
/*#################################*/
const ll N=50005;
ll n,k,ans;
ll f[N][505];
vector<ll> G[N];
void dfs(ll u,ll fa)
{
	f[u][0]=1;
	for(auto v:G[u])
	{
		if(v==fa)
			continue;
		dfs(v,u);
		rep(i,0,k-1)
			ans+=f[v][i]*f[u][k-i-1];
		rep(i,1,k)
			f[u][i]+=f[v][i-1];
	}
}
int main()
{
	read(n,k);
	ll u,v;
	rep(i,1,n-1)
	{
		read(u,v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1,0);
	OP(ans);
}
复制代码