P3806 【模板】点分治1

· · 题解

先贴一篇dalao的证明一种基于错误的寻找重心方法的点分治的复杂度分析%%%%%

针对本蒟蒻之前题解的一些错误以做出了修改，并且实测#7无RE/TLE，如果还有不到之处欢迎dalao指出

我们先随意指定一个根rt，将这棵树转化成有根树

不难发现树上的路径分为两类， 经过根节点rt的路径和包含于rt的某棵子树里(不经过rt)的路径

对于前者， 我们用dis[u]表示结点u到根节点rt的路径长度， 则u到v的路径长即为dis[u]+dis[v]

对于后者， 既然u到v的路径包含在rt的某个子树内， 那么我们就找到这棵子树的根，再对他求一次第一类路径

这样分治的思想就很明显了

就是把原来的树分成很多小的子树，并对每个子树分别求解第一类路径

点分治过程中，每一层的所有递归过程合计对每个点处理一次 假设共递归T层，则总时间复杂度为O(T*N)

然而，如果树退化成一条链 那么递归层数就是T=n，总时间复杂度为O(N^2)

这样显然不能承受，所以我们要让树的层数经量少 这里就要找树的重心

maxp[u] (max part)表示删除结点u后产生的子树中，最大的那棵的大小

则树的重心就是maxp[]值最小的那个节点

//sum是当前子树的总结点数，size[u]是以u为根的子树大小
void getrt(int u,int fa)
{
    size[u]=1; maxp[u]=0;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].v;
        if(v==fa||vis[v])continue;
        getrt(v,u);//先递归得到子树大小
        size[u]+=size[v];
        maxp[u]=max(maxp[u],size[v]);//更新u结点的maxp
    }
    maxp[u]=max(maxp[u],sum-size[u]);//考虑删除u后，父节点一侧的子树大小
    if(maxp[u]<maxp[rt]) rt=u;//更新当前子树的重心
}

我们在点分治过程中每次选取子树的重心为子树的树根进行处理， 这样总的递归深度不会超过logN层， 整个点分治的时间复杂度也就保证了O(NlogN)

点分治题的思想大都如上， 对于不同的题要设计不同的calc函数

回到本题，询问可以离线记录并直接在分治过程中处理

设当前根为rt，他的子树为v_1,v_2……v_t， 假设当前处理的子树为v_i，求出v_i中每个结点到rt的距离dis并保存于rem数组 并令judge[dis]表示在子树v_1~v_{i-1}中是否存在某个节点到rt距离为dis

遍历每个离线记录的询问，对每个询问遍历一次当前子树的rem 若当前询问距离为query[k]，遍历到的子树v_i中某个结点到rt距离为rem[j] 如果judge[query[k]-rem[j]]==1，则代表此询问的路径存在

再具体点解释这段话操作的含义 就是用子树v_i中某个结点与子树v_1~v_{i-1}中某个节点两两配对，检查是否存在长度为query[k]的路径

像这样配对完后将这棵子树的rem(即子树v_i中每个节点到rt的dis)一起保存进judge数组，继续下一个子树v_{i+1}的处理

当以rt为根的树查询完后清空judge数组 然后对其他子树进行分治

//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]d的路径存在就标记第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;
}