Topic background

Thank you for hzwer's point divide and rule mutual test.

Title Description

Given a tree with n points

Ask if there is a point pair with a distance of k on the tree.

I / O format

Input format:

n. M next n-1 edges a,b,c describe that a to b have a path of length c

Next line m asks a K for each line

Output format:

Output one answer for each K line, and there is output "AYE", otherwise output "NAY" (without quotation marks)

Example of input and output

2 1
1 2 2
2

AYE

Explain

For 30% of data n < = 100

For 60% of data n < = 1000, m < = 50

For 100% data, n < = 10000, m < = 100, C < = 1000, K < = 10000000

A kind of cooking made by my own YY

Slow as violence

We think about the process of divide and conquer,

The distance between one point and other points can be calculated quickly by point divide and conquer

In these distances, different subtrees can be added, and the same subtree can't be added. Special judgment is needed

For query operation, directly use array to record whether the point with the weight of $k $has occurred

#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;
}