模板题 P3806 【模板】点分治1

题目描述

给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。

详讲

关于点分治具体内容可以看这个
这里主要是详细讲讲代码：
getrt是用来求重心，我们利用树型dp的思维来做，即找到该节点所有的子树，找到最大的哪一颗即可

void getrt(int u,int pa)//求重心 
{
   
    size[u]=1; maxp[u]=0;
    for(int i=head[u];i;i=E[i].nxt) 
    {
   
        int v=E[i].v;
        if(v==pa||vis[v]) continue;
        getrt(v,u);
        size[u]+=size[v];
        maxp[u]=max(maxp[u],size[v]);
    }
    maxp[u]=max(maxp[u],sum-size[u]);
    if(maxp[u]<maxp[rt]) rt=u;
}

getdis是用来求每一个子节点到根的距离
getdis在calc中不断被调用

void getdis(int u,int fa)//每一个子节点到根的距离 
{
   
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=E[i].nxt)
    {
   
        int v=E[i].v;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+E[i].dis;
        getdis(v,u);
    }
}

calc是用来合并答案的，因为在getdis中已经计算出所有点到根的距离，所以把任意两个出现的距离凑在一起，并】、判断可否凑出我们需要的k即可
rem[i]存的是在getdis中求出的距离，rem[0]这个值是值rem存了多少值
judge我们可以用来存距离，对已经出现的距离用judge标记为1，这样当出现另一个距离可以和这个距离搭配成我们所需的k时，就可以直接标记答案
judge[query[k]-rem[j]];
query[k]-rem[j]即为所需要的距离

test[k]|=judge[query[k]-rem[j]];
用|就可以实现如果有就给test标记

void calc(int u)
{
   
    int p=0;
    for(int i=head[u];i;i=E[i].nxt)
    {
   
        int v=E[i].v;
        if(vis[v])continue;
        rem[0]=0; 
        dis[v]=E[i].dis;
        getdis(v,u);//处理u的每个子树的dis

        for(int j=rem[0];j;--j)//遍历当前子树的dis
        for(int k=1;k<=m;++k)//遍历每个询问
        {
   
	        if(query[k]>=rem[j])
	        
	        test[k]|=judge[query[k]-rem[j]];
	        //如果query[k]-rem[j]的路径存在就标记第k个询问
		}


        for(int j=rem[0];j;--j)//保存出现过的dis于judge
        {
   
        	q[++p]=rem[j];
			judge[rem[j]]=1;
		}
		 
        
    }
    for(int i=1;i<=p;++i)//处理完这个子树就清空judge
    judge[q[i]]=0;//特别注意一定不要用memeset，会T

}

solve则是对每一个根进行处理，通过solve来调用上述函数，在递归过程中不断重复一样的过程

void solve(int u)
{
      
    //judge[i]表示到根距离为i的路径是否存在
    vis[u]=judge[0]=1;
     calc(u);//处理以u为根的子树
    for(int i=head[u];i;i=E[i].nxt)//对每个子树进行分治
    {
   
        int v=E[i].v;
        if(vis[v])continue;
        sum=size[v]; 
		maxp[rt=0]=inf;//注意sum是以v为根的子树大小
        getrt(v,0);
		 solve(rt);//在子树中找重心并递归处理
    }
}

代码：

//niiick
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;

int read()
{
   
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){
   if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){
   x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int inf=10000000;
const int maxn=100010;
int n,m;
struct node{
   int v,dis,nxt;}E[maxn<<1];
int tot,head[maxn];
int maxp[maxn],size[maxn],dis[maxn],rem[maxn];
int vis[maxn],test[inf],judge[inf],q[maxn];
int query[1010];
int sum,rt;
int ans;

void add(int u,int v,int dis)
{
   
    E[++tot].nxt=head[u];
    E[tot].v=v;
    E[tot].dis=dis;
    head[u]=tot;
}

void getrt(int u,int pa)//求重心 
{
   
    size[u]=1; maxp[u]=0;
    for(int i=head[u];i;i=E[i].nxt) 
    {
   
        int v=E[i].v;
        if(v==pa||vis[v]) continue;
        getrt(v,u);
        size[u]+=size[v];
        maxp[u]=max(maxp[u],size[v]);
    }
    maxp[u]=max(maxp[u],sum-size[u]);
    if(maxp[u]<maxp[rt]) rt=u;
}

void getdis(int u,int fa)//每一个子节点到根的距离 
{
   
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=E[i].nxt)
    {
   
        int v=E[i].v;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+E[i].dis;
        getdis(v,u);
    }
}

void calc(int u)
{
   
    int p=0;
    for(int i=head[u];i;i=E[i].nxt)
    {
   
        int v=E[i].v;
        if(vis[v])continue;
        rem[0]=0; dis[v]=E[i].dis;
        getdis(v,u);//处理u的每个子树的dis

        for(int j=rem[0];j;--j)//遍历当前子树的dis
        for(int k=1;k<=m;++k)//遍历每个询问
        {
   
	        if(query[k]>=rem[j])
	        
	        test[k]|=judge[query[k]-rem[j]];
	        //如果query[k]-rem[j]的路径存在就标记第k个询问
		}


        for(int j=rem[0];j;--j)//保存出现过的dis于judge
        {
   
        	q[++p]=rem[j];
			judge[rem[j]]=1;
		}
		 
        
    }
    for(int i=1;i<=p;++i)//处理完这个子树就清空judge
    judge[q[i]]=0;//特别注意一定不要用memeset，会T

}

void solve(int u)
{
      
    //judge[i]表示到根距离为i的路径是否存在
    vis[u]=judge[0]=1; calc(u);//处理以u为根的子树
    for(int i=head[u];i;i=E[i].nxt)//对每个子树进行分治
    {
   
        int v=E[i].v;
        if(vis[v])continue;
        sum=size[v]; maxp[rt=0]=inf;//注意sum是以v为根的子树大小
        getrt(v,0); solve(rt);//在子树中找重心并递归处理
    }
}

int main()
{
   
    n=read();m=read();
    for(int i=1;i<n;++i)
    {
   
        int u=read(),v=read(),dis=read();
        add(u,v,dis);add(v,u,dis);
    }
    for(int i=1;i<=m;++i)
    query[i]=read();//先记录每个询问以离线处理

    maxp[rt]=sum=n;//第一次先找整棵树的重心
    getrt(1,0); 
    solve(rt);//对树进行点分治

    for(int i=1;i<=m;++i)
    {
   
        if(test[i]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}