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

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 Ruan_ji @ 2024-08-21 14:11:16

@Eriri 大佬能具体说说我这代码怎么改吗？然后您能再帮着看看我在main函数里的num和siz的赋值是正确的吗？

我有一个不明白的点就是我最开始的时候是随便弄一个点当根都行还是先getroot一下？我觉得随弄一个点当根可能就会对时间复杂度有影响罢？

by _Eriri_ @ 2024-08-21 15:04:37

@Ruan_ji 稍等,我帮你看一下

by _Eriri_ @ 2024-08-21 15:44:42

@Ruan_ji过了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#define INF 10000005
using namespace std;
const int N=2e4+5;

int n,m;
int ask[N];
struct node{
    int to,val;
};
vector<node> G[N];

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

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

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

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;mx[u]=0;
    pt[++pcnt]=u;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i].to;
        if(v==fa||del[v])continue;
        getroot(v,u);
        mx[u]=max(mx[u],siz[v]);
        siz[u]+=siz[v];
    }
    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){
    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;
        d[v]=G[u][i].val;
        cnt=0;
        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-5){
                q[++p]=dis[j];
                judge[dis[j]]=1;
            }
        }
    }
    for(int i=1;i<=p;++i)judge[q[i]]=0;
}
void divide(int u){
    pcnt=0;
    getroot(u,0);   
    int root=0;
    int maxn=1e9;
    for(int i=1;i<=pcnt;i++){
        int s=max(mx[pt[i]],siz[u]-siz[pt[i]]);
        if(s<maxn)maxn=s,root=pt[i];
    }
    del[root]=1;
    calc(root);
    for(int i=0;i<G[root].size();++i){
        int v=G[root][i].to;
        if(del[v])continue;
        divide(v);
    }
}

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);
        insert(v,u,w);
    }
    for(int i=1;i<=m;i++){      
        cin>>ask[i];
    }

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

by _Eriri_ @ 2024-08-21 15:45:02

@Ruan_ji 你的问题有点过于多了

by Ruan_ji @ 2024-08-21 15:48:11

@Eriri 谢谢大佬，我会自己仔细看的！小橘蒻感激不尽orz打扰了，刚刚去干了点事。

by Ruan_ji @ 2024-08-21 16:03:40

@Eriri 请问大佬pt是干啥的？

by _Eriri_ @ 2024-08-21 16:18:43

@Ruan_ji pt把dfs的点存在数组里

by Ruan_ji @ 2024-08-21 16:19:55

谢谢！