淀粉质 RE#7

record

其他都AC了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define mem(s) memset(s,0,sizeof(s))
#define F(i,l,r) for(i=l;i<=r;i++)
#define ll long long
using namespace std;
const int N=100005;
int n,r,i,j,siz,rt,ms=0x3f3f3f3f;
int size[N],vis[N],ans[10000123];
ll dist[N],arr[N],k;
namespace Graph {
    int first[N],nxt[N],to[N],val[N],top=0;
    void add(int u,int v,int z){
        to[++top]=v;
        nxt[top]=first[u];
        val[top]=z;
        first[u]=top;
        return ;
    }
}
#define _Graph(u) for(int i=Graph::first[u];i;i=Graph::nxt[i])
namespace IO {
    inline int read(){
        char ch=getchar();
        int x=0,f=1;
        while(ch<'0'||ch>'9'){
            if(ch=='-') f=-1;
            ch=getchar();
        }
        while('0'<=ch&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar();
        }
        return x*f;
    }
    inline void write(int x){
        if (x<0) x =~x+1,putchar('-');
        if (x>9) write(x/10);
        putchar(x%10+'0');
    }
}
void solve(int u,int fa){
    size[u]=1; int sonM=0;
    _Graph(u){
        int v=Graph::to[i];
        if(v==fa||vis[v]) continue;
        solve(v,u);
        size[u]+=size[v];
        sonM=max(sonM,size[v]);
    }
    sonM=max(sonM,siz-size[u]);
    if(sonM<ms){
        ms=sonM,rt=u;
    }
    return ;
}
void prepare(int u,int fa){
    arr[++r]=dist[u];
    _Graph(u){
        int v=Graph::to[i];
        if(v==fa||vis[v]) continue;
        dist[v]=dist[u]+Graph::val[i];
        prepare(v,u);
    }
    return ;
}
void calc(int u,int val,int tag){
    ll sum=0;
    r=0,dist[u]=val,prepare(u,0);
    for(int i=1;i<=r;i++){
      for(int j=i+1;j<=r;j++)
         ans[arr[i]+arr[j]]+=tag;
    }
    return ;
}
void dfs(int u){
    calc(u,0,1);
    vis[u]=1;
    _Graph(u){
        int v=Graph::to[i];
        if(vis[v]) continue;
        calc(v,Graph::val[i],-1);
        siz=size[v];
        ms=0x3f3f3f3f;
        solve(v,0);
        dfs(rt);
    }
}
int main() {
    n=IO::read(); k=IO::read(); siz=n;
    for(int i=1;i<n;i++){
        int x=IO::read(),y=IO::read(),z=IO::read();
        Graph::add(x,y,z),Graph::add(y,x,z);
    }
    solve(1,0);
    dfs(rt);
    while(k--) {
      printf(ans[IO::read()]?"AYE\n":"NAY\n");
    }
    return 0;
}