萌新袜子求调，在线等呦（柯爱的点分治）

Ruan_ji @ 2024-08-21 12:03:18

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#define INF 1e7+5
using namespace std;

int n,m;
int ask[105];

struct node{
    int to,val;
};
vector<node> G[10005];

//分治
int root,mxs,num;
int siz[10005];//以这个点为根的子树的大小
int del[10005];//已经贡献过的根结点，可以删掉了

//找出各个点到根的距离
int dis[10005];
int d[10005]; //辅助
int cnt; //记录预处理了距离的数量

int ans[105];//答案
int q[10005]; //队列
bool judge[10005]; //判断距离是否存在

void insert(int u,int v,int w){
    node dott;
    dott.to=v;
    dott.val=w;
    G[u].push_back(dott);
    return ;
}

void getroot(int u,int fa){
    siz[u]=1;
    int s=0;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(v==fa||del[v]){
            continue;
        }
        getroot(v,u);
        siz[u]+=siz[v];
        s=max(s,siz[v]);
    }
    s=max(s,num-siz[u]);
    if(s<mxs){
        mxs=s;
        root=u;
    }
    return ;
}

void getdis(int u,int fa){
    dis[++cnt]=d[u];
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(v==fa||del[v]){
            continue;
        }
        d[v]=d[u]+G[u][i].val;
        getdis(v,u);
    }
}

void calc(int u){
    del[u]=1;
    judge[0]=1;
    int p=0;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(del[v]){
            continue;
        }

        cnt=0;
        d[v]=G[u][i].val;
        getdis(v,u);
        for(int j=1;j<=cnt;++j){
            for(int k=1;k<=m;++k){
                if(ask[k]>=dis[j]){
                    ans[k]|=judge[ask[k]-dis[j]];
                }
            }
        }
        for(int j=1;j<=cnt;++j){
            if(dis[j]<=INF){
                q[++p]=dis[j];
                judge[dis[j]]=1;
            }
        }
    }

    for(int i=1;i<=p;++i){
        judge[q[i]]=0;
    }
}

void divide(int u){
    calc(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(del[v]){
            continue;
        }
        num=mxs=siz[v];
        getroot(v,0);
        divide(root);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v,w;cin>>u>>v>>w;
        insert(u,v,w);
    }
    int i=0;
    int kk=m;
    while(kk--){
        cin>>ask[++i];
    }

    getroot(1,0);
    divide(root);

    for(int i=1;i<=m;++i){
        if(ans[i]==0){
            cout<<"AYE"<<'\n';
        }
        else{
            cout<<"NAY"<<'\n';
        }
    }
    return 0;
}

by _Eriri_ @ 2024-08-21 12:34:41

你真的是袜子吗？？可不可以让我吃

by __galaxy_1202__ @ 2024-08-21 12:39:44

本人袜子是不是违规了

by _Eriri_ @ 2024-08-21 12:44:02

你的num怎么没赋过值呢

by _Eriri_ @ 2024-08-21 12:46:00

你的root一定是0,应为mxs也没赋过值

by _Eriri_ @ 2024-08-21 12:46:19

@Ruan_ji

by Ruan_ji @ 2024-08-21 13:47:41

@Eriri 谢谢

by Ruan_ji @ 2024-08-21 13:48:25

@Eriri 大佬orz关注了

by Ruan_ji @ 2024-08-21 13:54:43

@Eriri 大老您看看我下面的这个改对了吗？

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#define INF 1e7+5
using namespace std;

int n,m;
int ask[105];

struct node{
    int to,val;
};
vector<node> G[10005];

//分治
int root,mxs,num;
int siz[10005];//以这个点为根的子树的大小
int del[10005];//已经贡献过的根结点，可以删掉了

//找出各个点到根的距离
int dis[10005];
int d[10005]; //辅助
int cnt; //记录预处理了距离的数量

int ans[105];//答案
int q[10005]; //队列
bool judge[10005]; //判断距离是否存在

void insert(int u,int v,int w){
    node dott;
    dott.to=v;
    dott.val=w;
    G[u].push_back(dott);
    return ;
}

void getroot(int u,int fa){
    siz[u]=1;
    int s=0;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(v==fa||del[v]){
            continue;
        }
        getroot(v,u);
        siz[u]+=siz[v];
        s=max(s,siz[v]);
    }
    s=max(s,num-siz[u]);
    if(s<mxs){
        mxs=s;
        root=u;
    }
    return ;
}

void getdis(int u,int fa){
    dis[++cnt]=d[u];
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(v==fa||del[v]){
            continue;
        }
        d[v]=d[u]+G[u][i].val;
        getdis(v,u);
    }
}

void calc(int u){
    del[u]=1;
    judge[0]=1;
    int p=0;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(del[v]){
            continue;
        }

        cnt=0;
        d[v]=G[u][i].val;
        getdis(v,u);
        for(int j=1;j<=cnt;++j){
            for(int k=1;k<=m;++k){
                if(ask[k]>=dis[j]){
                    ans[k]|=judge[ask[k]-dis[j]];
                }
            }
        }
        for(int j=1;j<=cnt;++j){
            if(dis[j]<=INF){
                q[++p]=dis[j];
                judge[dis[j]]=1;
            }
        }
    }

    for(int i=1;i<=p;++i){
        judge[q[i]]=0;
    }
}

void divide(int u){
    calc(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(del[v]){
            continue;
        }
        num=mxs=siz[v];
        getroot(v,0);
        divide(root);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;++i){
        int u,v,w;cin>>u>>v>>w;
        insert(u,v,w);
    }
    int i=0;
    int kk=m;
    while(kk--){
        cin>>ask[++i];
    }

    mxs=n;
    num=n;
    getroot(1,0);
    divide(0);

    for(int i=1;i<=m;++i){
        if(ans[i]==1){
            cout<<"AYE"<<'\n';
        }
        else{
            cout<<"NAY"<<'\n';
        }
    }
    return 0;
}

by Ruan_ji @ 2024-08-21 13:59:50

@Ruan_ji 我也不知道咋改啊，样例都没过，不好意思啊

by _Eriri_ @ 2024-08-21 14:02:52

@Ruan_ji 我觉得你这个有个比较大的问题，你完全可以不在主函数里求一个重心再递归，你可以直接在divide的时候getroot(u)当做根。而且num和mxs不该赋值成siz[v]，这是换根前的size，换了根后真正的size已经变了