淀粉质板子求调

Nemonade @ 2022-06-02 20:00:19

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define pfor(i,x,y) for(register int i=x;i<=y;++i)
#define mfor(i,x,y) for(register int i=x;i>=y;--i)
constexpr inline int maxx(const int &x,const int &y){return x>y?x:y;}
constexpr inline int minx(const int &x,const int &y){return x<y?x:y;}
constexpr inline int absx(const int &x){return (x>0)?(x):(~x+1);}
inline int read(){
    int x=0;bool flag=false;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return flag?~x+1:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=(~x+1);}
    if(x/10) write(x/10);
    putchar((x%10)^48);
    return;
}
const int N=1e4+5,M=1e2+5;
int n,m,x,y,z,mx[N],size[N],root,dist[N],q[N],tmp[N],tot;
int head[N],nxt[N<<1],ver[N<<1],edge[N<<1],tote;
vector<int> v;
bool vis[N],out[M],res[N<<12];
inline void add(int x,int y,int z){
    ver[++tote]=y,edge[tote]=z;
    nxt[tote]=head[x],head[x]=tote;
    return;
}
inline void getroot(int x,int fa,int num){
    mx[x]=0,size[x]=1;
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(y==fa||vis[y]) continue;
        getroot(y,x,num);
        size[x]+=size[y],mx[x]=maxx(mx[x],size[y]);
    }
    mx[x]=maxx(mx[x],num-size[x]);
    if(mx[x]<mx[root]) root=x;
    return;
}
inline void getsize(int x,int fa){
    v.push_back(dist[x]);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(y==fa||vis[y]) continue;
        dist[y]=dist[x]+edge[i];
        getsize(y,x);
    }
    return;
}
inline void calc(int x){
    tot=0;
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        dist[y]=edge[i];
        v.clear();
        getsize(y,-114514);
        pfor(j,0,v.size()-1) pfor(k,1,m) if(q[k]>=v[j]) out[k]|=res[q[k]-v[j]];
        pfor(j,0,v.size()-1) tmp[++tot]=v[j],res[v[j]]=true;
    }
    pfor(i,1,tot) res[tmp[i]]=false;
    return;
}
inline void solve(int x){
    vis[x]=res[0]=true;
    calc(x);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        mx[root=0]=INT_MAX;
        getroot(y,x,size[y]);
        solve(root);
    }
    return;
}
signed main(){
    n=read(),m=read();
    pfor(i,1,n-1){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    pfor(i,1,m) q[i]=read();
    mx[root=0]=INT_MAX;
    getroot(1,-114514,n);
    solve(root);
    pfor(i,1,m) puts(out[i]?"AYE":"NAY");
    return 0;
}

by Nemonade @ 2022-06-02 21:15:38

大佬我消化一会，谢谢啦

by LCATreap @ 2022-06-02 21:15:44

确实是 getroot 写挂了，我把正确代码的复制上去 A 了。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define pfor(i,x,y) for(register int i=x;i<=y;++i)
#define mfor(i,x,y) for(register int i=x;i>=y;--i)
constexpr inline int maxx(const int &x,const int &y){return x>y?x:y;}
constexpr inline int minx(const int &x,const int &y){return x<y?x:y;}
constexpr inline int absx(const int &x){return (x>0)?(x):(~x+1);}
inline int read(){
    int x=0;bool flag=false;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') flag=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return flag?~x+1:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=(~x+1);}
    if(x/10) write(x/10);
    putchar((x%10)^48);
    return;
}
const int N=1e4+5,M=1e2+5;
int n,m,x,y,z,mx[N],size[N],root,dist[N],q[N],tmp[N],tot,num=0;
int head[N],nxt[N<<1],ver[N<<1],edge[N<<1],tote;
vector<int> v;
bool vis[N],out[M],res[N<<12];
inline void add(int x,int y,int z){
    ver[++tote]=y,edge[tote]=z;
    nxt[tote]=head[x],head[x]=tote;
    return;
}
void getroot(int u, int f = 0){
    size[u] = 1, mx[u] = 0; int v;
    for(int i = head[u]; i; i = nxt[i]){
        v = ver[i];
        if(v == f || vis[v])continue;
        getroot(v, u);
        size[u] += size[v];
        if(size[v] > mx[u])mx[u] = size[v]; 
    }
    mx[u] = max(mx[u], num - size[u]);
    if(mx[u] < mx[root])root = u;
}

inline void getsize(int x,int fa){
    v.push_back(dist[x]);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(y==fa||vis[y]) continue;
        dist[y]=dist[x]+edge[i];
        getsize(y,x);
    }
    return;
}
inline void calc(int x){
    tot=0;
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        dist[y]=edge[i];
        v.clear();
        getsize(y,-114514);
        pfor(j,0,v.size()-1) pfor(k,1,m) if(q[k]>=v[j]) out[k]|=res[q[k]-v[j]];
        pfor(j,0,v.size()-1) tmp[++tot]=v[j],res[v[j]]=true;
    }
    pfor(i,1,tot) res[tmp[i]]=false;
    return;
}
inline void solve(int x){
    vis[x]=res[0]=true;
    calc(x);
    for(register int i=head[x];i;i=nxt[i]){
        y=ver[i];
        if(vis[y]) continue;
        mx[root=0]=num=size[y];
        getroot(y,x);
        solve(root);
    }
    return;
}
signed main(){
    n=read(),m=read();
    pfor(i,1,n-1){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    pfor(i,1,m) q[i]=read();
    mx[root=0]=num=n;
    getroot(1,0);
    solve(root);
    pfor(i,1,m) puts(out[i]?"AYE":"NAY");
    return 0;
}

by Nemonade @ 2022-06-02 21:45:30

@wqlGZZC 谢谢大佬，已经回关注