algorithm

Point divide and conquer is used to deal with large tree paths. The approximate process of the algorithm is to take the center of gravity of a tree as the root, first maintain the answers contributed by the path through the root, and then delete the center of gravity to obtain several subtrees, and repeat the above process for these subtrees. The complexity is O(Nlog⁡N)O(N\log N)O(NlogN) (if the center of gravity is selected, log⁡N\log NlogN layers can be reached, and the sum of complexity of each layer is O(N)O(N)O(N) O(N)).

sample

【 template 】 Point divide and conquer 1

P3806 【 template 】 Point divide and conquer 1

code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(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(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }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(a)
{
	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");
}
Copy the code

Codeforces VK Cup 2012 Round 1 D. Distance in Tree

Train of thought

Divide-and-conquer naked problem. F [u][I] F [u][I] F [u][I]f[u][I]f[u][I] is the number of points whose distance from UUu point is iii. Before maintaining the contribution of a node VVV to UUu, calculate its contribution to the answer first, so that there will be no round-trip path.

Divide-and-conquer code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(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(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }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(a)
{
	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);
}
Copy the code

Tree DP code

#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(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(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
    int__ =0; _ =0;
    char ch=getchar(a);while(!isdigit(ch))
    {
        if(ch==The '-') __ =1;
        ch=getchar(a); }while(isdigit(ch))
    {
        _=_*10+ch- 48;
        ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
    if(_ <0)
    {
        putchar(The '-'); _ = - _; }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(a)
{
	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);
}
Copy the code

Examples continue to be updated.

Reference blog: 1 2