洛谷 P3806 【模闆】點分治1

​​題目傳送門​​

#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=10000+100;
const int maxm=10000000+100;

bool kaven[maxm],vis[maxn];
struct Edge{
    
    int to,len,next;
}edge[maxn<<1];
int head[maxn],tot;
int son[maxn],dis[maxn];
int root,all,num;
int n,m;
struct Node{
    
    int id,dis;
}node[maxn];
int Id,nodenum;

void Add(int u,int v,int len){
    
    edge[tot].to=v;
    edge[tot].len=len;
    edge[tot].next=head[u];
    head[u]=tot++;
    
    edge[tot].to=u;
    edge[tot].len=len;
    edge[tot].next=head[v];
    head[v]=tot++;
}
//得到目前這棵樹的重心
void DFS(int u,int fa){
    
    son[u]=1;
    int maxson=0;
    for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        int v=e.to;
        if(v==fa || vis[v]) continue;
        son[u]+=son[v];
        maxson=max(maxson,son[v]);
    }
    maxson=max(maxson,all-son[u]);
    if(maxson<num) root=u,num=maxson;
}

//計算結點到目前樹 root 的距離 (以前進行過點分治的除外，不然會有大量重複計算) 
void getDis(int rot,int u,int fa,int id){
    
    for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        int v=e.to,len=e.len;
        if(vis[v] || v==fa) continue;
        dis[v]=dis[u]+len;
        if(rot==u) node[nodenum].dis=dis[v],node[nodenum++].id= ++Id;  //root的孩子結點是 root這棵樹的子樹的根,是以++Id 對子樹根進行編号 
        else node[nodenum].dis=dis[v],node[nodenum++].id= id;   //子樹非根結點編号為子樹根結點的編号 
        kaven[dis[v]]=true;
        if(rot==u) getDis(rot,v,u,Id);
        else getDis(rot,v,u,id);
    }
}

//點分治 
void getNode(int u){
    
    dis[u]=0;
    vis[u]=true;
    Id=nodenum=0;  //Id:對樹根為 root 的每棵子樹進行編号（以前進行過點分治的除外），在同一棵子樹上的結點編号相同 
    getDis(root,u,-1,0); 
    for(int i=0;i<nodenum;i++){
        
        for(int j=i+1;j<nodenum;j++){
            
            if(node[i].id!=node[j].id) kaven[node[i].dis+node[j].dis]=true;   //不同子樹結點之間的距離 
        }
    }
    for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        int v=e.to;
        if(vis[v]) continue;
        root=0;all=son[v];num=INF;  //初始化  
        DFS(v,-1);         //找子樹的重心 
        getNode(root);     //子樹進行點分治
    }
}

int main(){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) head[i]=-1;
    tot=0;root=0;num=INF;all=n;
    for(int i=1;i<n;i++){
        
        int u,v,len;
        scanf("%d%d%d",&u,&v,&len);
        Add(u,v,len);
    }
    DFS(1,-1);
    getNode(root);
    for(int i=1,k;i<=m;i++) scanf("%d",&k),printf("%s\n",kaven[k]?"AYE":"NAY");
}