模板求调&悬关

Sad_Rex @ 2023-07-24 10:58:47

#include<bits/stdc++.h>
//#pragma GCC optimize(3, "Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
//#define int long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
    int vis=1,ans=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-')vis=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        ans=ans*10+x-'0';
        x=getchar();
    }
    return vis*ans;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int n=read(),m=read();
const int N=1e4+9;
int u,v,w;
int minn=INT_MAX;
struct node{
    int nxt,to,w;
}e[2*N];
int head[N],cnt;
inline void add(int x,int y,int w){
    ++cnt;
    e[cnt].to=y;
    e[cnt].nxt=head[x];
    e[cnt].w=w;
    head[x]=cnt;
}
int root,size[N],maxnson[N];
bool vis[N];
int tmp=0,dis[N];
int Sumnode;
int num[N];
inline void get_heavy(int p,int fa){
    size[p]=1,maxnson[p]=0;
    for(int i=head[p];i;i=e[i].nxt){
        int y=e[i].to;
        if(vis[y]||y==fa)continue;
        get_heavy(y,p);
        size[p]+=size[y];
        maxnson[p]=max(maxnson[p],size[y]);
    }
    maxnson[p]=max(maxnson[p],Sumnode-size[p]);
    if(maxnson[p]<minn)minn=maxnson[p],root=p;
}
inline void ask(int begin,int fa,int len){
    dis[++tmp]=len;
    for(int i=head[begin];i;i=e[i].nxt){
        int y=e[i].to;
        if(vis[y]||y==fa)continue;
        ask(y,begin,len+e[i].w);
    }
}
inline void init(int p,int len,bool f){
    tmp=0;
    ask(p,-1,0);
    if(f){
        for(int i=1;i<tmp;i++){
            for(int j=i+1;j<=tmp;j++){
                num[dis[i]+dis[j]]++;
            }
        }
    }else{
        for(int i=1;i<tmp;i++){
            for(int j=i+1;j<=tmp;j++){
                num[dis[i]+dis[j]]--;
            }
        }
    }
}
inline void difen(int p){
    vis[p]=1;
    init(p,0,1);
    for(int i=head[p];i;i=e[i].nxt){
        int y=e[p].to;
        if(vis[y])continue;
        init(y,e[i].w,0);
        minn=INT_MAX,root=0,Sumnode=size[y];
        get_heavy(y,-1);
        difen(root);
    }
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    Sumnode=n;
    for(int i=1;i<n;i++){
        u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    get_heavy(1,-1);
    difen(root);
    while(m--){
        int k=read();
        if(num[k])puts("AYE");
        else puts("NAY");
    }
    return 0;
}
/*
2 1
1 2 2
2
*/

by Sad_Rex @ 2023-07-24 11:13:02

#include<bits/stdc++.h>
//#pragma GCC optimize(3, "Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
#define int long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
    int vis=1,ans=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-')vis=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        ans=ans*10+x-'0';
        x=getchar();
    }
    return vis*ans;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
int n=read(),m=read();
const int N=1e4+9,M=1e7+9;
int u,v,w;
int minn=INT_MAX;
struct node{
    int nxt,to,w;
}e[2*N];
int head[N],cnt;
inline void add(int x,int y,int w){
    ++cnt;
    e[cnt].to=y;
    e[cnt].nxt=head[x];
    e[cnt].w=w;
    head[x]=cnt;
}
int root,size[N],maxnson[N];
bool vis[N];
int tmp=0,dis[N];
int Sumnode;
int num[M];
inline void get_heavy(int p,int fa){
    size[p]=1,maxnson[p]=0;
    for(int i=head[p];i;i=e[i].nxt){
        int y=e[i].to;
        if(vis[y]||y==fa)continue;
        get_heavy(y,p);
        size[p]+=size[y];
        maxnson[p]=max(maxnson[p],size[y]);
    }
    maxnson[p]=max(maxnson[p],Sumnode-size[p]);
    if(maxnson[p]<minn)minn=maxnson[p],root=p;
}
inline void ask(int begin,int fa,int len){
    dis[++tmp]=len;
    for(int i=head[begin];i;i=e[i].nxt){
        int y=e[i].to;
        if(vis[y]||y==fa)continue;
        ask(y,begin,len+e[i].w);
    }
}
inline void init(int p,int len,bool f){
    tmp=0;
    ask(p,-1,0);
    if(f){
        for(int i=1;i<tmp;i++){
            for(int j=i+1;j<=tmp;j++){
                num[dis[i]+dis[j]]++;
            }
        }
    }else{
        for(int i=1;i<tmp;i++){
            for(int j=i+1;j<=tmp;j++){
                num[dis[i]+dis[j]]--;
            }
        }
    }
}
inline void difen(int p){
    vis[p]=1;
    init(p,0,1);
    for(int i=head[p];i;i=e[i].nxt){
        int y=e[p].to;
        if(vis[y])continue;
        init(y,e[i].w,0);
        minn=INT_MAX,root=0,Sumnode=size[y];
        get_heavy(y,-1);
        difen(root);
    }
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    Sumnode=n;
    for(int i=1;i<n;i++){
        u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    get_heavy(1,-1);
    difen(root);
    while(m--){
        int k=read();
        if(num[k])puts("AYE");
        else puts("NAY");
    }
    return 0;
}
/*
2 1
1 2 2
2
*/

by InversionShadow @ 2023-07-24 11:44:53

卷