#7#9TLE点分值求调,悬关
查看原帖
#7#9TLE点分值求调,悬关
749175
114514xxx楼主2025/1/23 18:01
#include<bits/stdc++.h>
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N=1e5+25;
struct Edge{
    int to,next,w;
}edge[N];
int head[N],cnt,dp[N],tot;
int vis[N],dis[N],rem[N],q[N];
int query[N],siz[N],root;
int n,m;
bool test[N];
char *p1,*p2,buf[1<<21];
bitset<N*1000>judge;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57){
        if(ch=='-')f*=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57) x=x*10+ch-48,ch=getchar();
	return x*f;
}
inline void add(int x,int y,int z){
    edge[++cnt]={y,head[x],z};
    head[x]=cnt;
}
inline void getroot(int u,int fa){
    siz[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa||vis[v])continue;
        getroot(v,u);
        siz[u]+=siz[v];
        dp[u]=max(dp[u],siz[v]);
    }
    dp[u]=max(tot-dp[u],dp[u]);
    if(dp[u]<dp[root])root=u;
}
inline void getdis(int u,int fa){
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+edge[i].w;
        getdis(v,u);
    }
}
inline void calc(int u){
    int p=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v])continue;
        rem[0]=0;dis[v]=edge[i].w;
        getdis(v,u);
        for(int j=rem[0];j;--j)
            for(int k=1;k<=m;++k)
                if(query[k]>=rem[j])
                    test[k]|=judge[query[k]-rem[j]];
        for(int j=rem[0];j;--j)
            q[++p]=rem[j],judge[rem[j]]=1;
    }
    for(int i=1;i<=p;++i)
        judge[q[i]]=0;
}
inline void solve(int u){
    vis[u]=judge[0]=1;calc(u);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(vis[v])continue;
        tot=siz[v];root=0;dp[root]=N*10;
        getroot(v,0);solve(root);
    }
}
int main(){
    //freopen("divide2.in","r",stdin);
    cin>>n>>m;
    int x,y,z;
    for(int i=1;i<n;i++){
        x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=m;i++)query[i]=read();
    dp[root]=tot=n;
    getroot(1,0);
    solve(root);
    for(int i=1;i<=m;i++)
        if(test[i])cout<<"AYE\n";else cout<<"NAY\n";
}

2025/1/23 18:01
加载中...