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

· · 题解

前言

似乎很早以前就学过了，但是一直没写博客，现在来补一下锅。

分治

我们首先随便就选择一个点当做根节点

显然，这棵树里面有这么两种具有特定性质的边

1.穿过根节点的路径

2.不穿过根节点的路径

对于第1类的点，我们可以用dis[u]表示从点u到目前根节点的距离，

那么穿过根节点的路径的距离就是dis[u]+dis[v]。

而第2类的点我们可以再次在这个子树里面再寻找一个根节点，重复第1类点所做的事。

由此可见，分治的思想就很显然了。

树的重心

但是如果直接这样求，时间复杂度可能会退化直到n方，这是我们所不能接受的。

所以我们需要求出这一棵树的重心，可以使每一小棵树递归的时间为log n

代码

#include<iostream>
#include<cstdio>
#define maxn 100010
#define inf 100000000
#define re register
using namespace std;
inline int read()
{
    int p=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-') f*=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())
        p=p*10+ch-48;
    return p*f;
}
struct node
{
    int v,dis,next;
}edge[maxn<<1];
int tot,st[maxn],mroot[maxn],size[maxn],dis[maxn],nowd[maxn],n,m;
int vis[maxn],lans[inf],judge[inf],q[maxn],query[1010],sum,root,ans;
void add(int u,int v,int dis)
{
    edge[++tot].next=st[u];
    edge[tot].v=v;
    edge[tot].dis=dis;
    st[u]=tot;
}
void getroot(int u,int pa)
{
    size[u]=1;mroot[u]=0;
    for(re int i=st[u];i;i=edge[i].next) 
    {
        re int v=edge[i].v;
        if (v==pa||vis[v]) 
            continue;
        getroot(v,u);
        size[u]+=size[v];
        mroot[u]=max(mroot[u],size[v]);
    }
    mroot[u]=max(mroot[u],sum-size[u]);
    if (mroot[u]<mroot[root]) 
        root=u;
}
void getdis(int u,int fa)
{
    nowd[++nowd[0]]=dis[u];
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+edge[i].dis;
        getdis(v,u);
    }
}
void calc(int u)
{
    re int p=0;
    for (re int i=st[u];i!=0;i=edge[i].next)
    {
        re int v=edge[i].v;
        if (vis[v])
            continue;
        nowd[0]=0;dis[v]=edge[i].dis;
        getdis(v,u);
        for(re int j=nowd[0];j!=0;j--)
            for(re int k=1;k<=m;k++)
                if (query[k]>=nowd[j])
                    lans[k]|=judge[query[k]-nowd[j]];
        for(re int j=nowd[0];j!=0;j--)
        {
            q[++p]=nowd[j];
            judge[nowd[j]]=1;
        }
    }
    for(re int i=1;i<=p;i++)
        judge[q[i]]=0;

}
void solve(int u)
{   
    vis[u]=judge[0]=1;
    calc(u);
    for(re int i=st[u];i;i=edge[i].next)
    {
        re int v=edge[i].v;
        if (vis[v])
            continue;
        sum=size[v]; 
        mroot[root=0]=inf;
        getroot(v,0); 
        solve(root);
    }
}
int main()
{
    n=read();m=read();
    for(re int i=1;i<n;i++)
    {
        re int u=read(),v=read(),dis=read();
        add(u,v,dis);add(v,u,dis);
    }
    for(re int i=1;i<=m;i++)
        query[i]=read();
    mroot[root]=sum=n;
    getroot(1,0); 
    solve(root);
    for (re int i=1;i<=m;i++)
    {
        if (lans[i]) 
            printf("AYE\n");
        else 
            printf("NAY\n");
    }
}