洛谷P3806 【模板】點分治1

題目背景

感謝hzwer的點分治互測。

題目描述

給定一棵有n個點的樹

詢問樹上距離為k的點對是否存在。

輸入輸出格式

輸入格式：

n,m 接下來n-1條邊a,b,c描述a到b有一條長度為c的路徑

接下來m行每行詢問一個K

輸出格式：

對於每個K每行輸出一個答案，存在輸出“AYE”,否則輸出”NAY”(不包含引號)

輸入輸出樣例

2 1
1 2 2
2

AYE

說明

對於30%的數據n<=100

對於60%的數據n<=1000,m<=50

對於100%的數據n<=10000,m<=100,c<=1000,K<=10000000

自己YY出來的一種做法

慢的跟暴力一樣

我們考慮點分治的過程，

用點分治可以快速計算出一個點到其他點的距離

在這些距離中，不同子樹的可以相加，同一子樹的不能相加，需要特判

對於查詢操作，直接用數組記錄權值為$k$的點是否出現過

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=1e6+10;
const int INF=1e7+10;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN];
int num=1;
inline void AddEdge(int x,int y,int z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int F[MAXN],sum,siz[MAXN],vis[MAXN],root=0,cnt=0,deep[MAXN],can[MAXN];
struct Ans
{
    int v,id;
}tot[MAXN];
void GetRoot(int now,int fa)
{
    siz[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]||edge[i].v==fa) continue;
        GetRoot(edge[i].v,now);
        siz[now]+=siz[edge[i].v];
        F[now]=max(F[now],siz[edge[i].v]);
    }
    F[now]=max(F[now],sum-F[now]);
    if(F[now]<F[root]) root=now;
}
void GetDeep(int now,int fa,int NowDeep,int num)
{
    int cur=0;
    tot[++cnt].v=deep[now];
    tot[cnt].id=num;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]||edge[i].v==fa) continue;
        deep[edge[i].v]=deep[now]+edge[i].w;
        if(NowDeep!=1) GetDeep(edge[i].v,now,NowDeep+1,num);
        else GetDeep(edge[i].v,now,NowDeep+1,cur++);
    }
}
void Work(int now)
{
    cnt=0;deep[now]=0;
    GetDeep(now,0,1,1);
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt;j++)
            if(tot[i].id!=tot[j].id) 
                 can[tot[i].v+tot[j].v]=1;
            else can[tot[i].v]=1,can[tot[j].v]=1;
}
void Solve(int now)
{
    Work(now);
    vis[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(vis[edge[i].v]) continue;
        root=0;
        sum=siz[edge[i].v];
        GetRoot(edge[i].v,0);
        Solve(edge[i].v);
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif 
    memset(head,-1,sizeof(head));
    int N=read(),M=read();
    for(int i=1;i<=N-1;i++)
    {
        int x=read(),y=read(),z=read();
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    root=0;
    F[0]=INF;
    sum=N;
    GetRoot(1,0);
    Solve(root);
    for(int i=1;i<=M;i++)
    {
        int p=read();
        if(can[p]) printf("AYE\n");
        else        printf("NAY\n");
    }
    return 0;
}