刚学OI，不会点分治

P3806 【模板】点分治 1

钱逸凡 @ 2020-11-22 19:28:41

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
} 
const int mx=10100;
int n,m;
struct Edge{
    int v;
    int val;
    int next;
}edge[mx<<1];
int top,head[mx];
void addedge(int u,int v,int val){
    edge[++top].v=v;
    edge[top].next=head[u];
    edge[top].val=val;
    head[u]=top;
}
void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,val);
}
int size[mx],maxn[mx];//每个点的子节点数量,每个点最大的子树大小 
int s;//当前树的点的总数 
int vis[mx];//该点是否被访问过 
int dist[mx];//每个点到重心的距离 
int root;//重心（分治中心） 
struct Path{
    int lenth;//路径长度
    int from;//从重心的哪个子节点出发的 
}path[mx];
bool cmp(Path a,Path b){
    return a.lenth<b.lenth;//按照路径长度排序 
}
int q[mx];//所有的询问 
int ans[mx];//询问是否成立 
int cnt;//当前路径数量 
void find(int u,int fa){//寻找当前树的重心 
    maxn[u]=0,size[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa||vis[v])continue;//防止回到已经找过的区域 
        find(v,u);
        size[u]+=size[v];
        maxn[u]=max(maxn[u],size[v]);
    }
    maxn[u]=max(maxn[u],s-size[u]);//可能往上是最大的子树 
    if(maxn[u]<maxn[root])root=u;//更新重心 
}
void get_dist(int u,int fa,int start){
    path[++cnt]=(Path){dist[u],start};
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa||vis[v])continue;
        dist[v]=dist[u]+edge[i].val;
        get_dist(v,u,start);
    }
}
void cal(int u){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        dist[v]=edge[i].val;
        get_dist(v,u,v);
    }
    sort(path+1,path+1+cnt,cmp);
    for(int i=1;i<=m;++i){//遍历所有询问 
        if(ans[i])continue;//其他子树中已经有该长度的路径了 
        for(int j=1;j<=cnt;++j){//先看看单条路径是否符合要求
            if(path[j].lenth==q[i]){
                ans[i]=1;
                break;
            }
        }
        if(ans[i])continue;//已经符合要求了就不用看两条路径相加了 
        int l=1,r=cnt;
        while(l<r){
            if(path[l].lenth+path[r].lenth<q[i])++l;//小了就左端点右移 
            else if(path[l].lenth+path[r].lenth>q[i])--r;//大了就右端点左移 
            else{
                if(path[l].from==path[r].from){//同一个子节点出发的路径不能相加
                    if(path[r].lenth==path[r-1].lenth)--r;
                    else if(path[l].lenth==path[l+1].lenth)++l;
                    else break; 
                }
                else{//找到了符合要求的路径 
                    ans[i]=1;
                    break;
                }
            }
        }
    }

}
void solve(int u){
    vis[u]=1;//标记已经找过 
    cnt=0;//清空no 
    cal(u);//以当前节点为重心计算一次 
    int ss=s;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        s=size[v];
        if(size[v]>size[u])s=ss-size[u];
        root=0;
        maxn[0]=1<<30;//不能使0为重心 
        find(v,0);//找到子树的重心
        solve(root);//按照子树的重心重复操作 
    }
}
int main(){
//  freopen("in.txt","r",stdin);
    n=Read(),m=Read();
    for(int i=1;i<n;++i){
        int u=Read(),v=Read(),val=Read();
        add(u,v,val);
    }
    for(int i=1;i<=m;++i)q[i]=Read();
    maxn[0]=1<<30;//防止把0当成重心 
    find(1,0);//找初始重心 
    solve(root);
    for(int i=1;i<=m;++i)printf("%s\n",(ans[i]?"AYE":"NAY"));
    return 0;
}

这是一个T了的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
} 
const int mx=10100;
int n,m;
struct Edge{
    int v;
    int val;
    int next;
}edge[mx<<1];
int top,head[mx];
void addedge(int u,int v,int val){
    edge[++top].v=v;
    edge[top].next=head[u];
    edge[top].val=val;
    head[u]=top;
}
void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,val);
}
int size[mx],maxn[mx];//每个点的子节点数量,每个点最大的子树大小 
int s;//当前树的点的总数 
int vis[mx];//该点是否被访问过 
int dist[mx];//每个点到重心的距离 
int root;//重心（分治中心） 
struct Path{
    int lenth;//路径长度
    int from;//从重心的哪个子节点出发的 
}path[mx];
bool cmp(Path a,Path b){
    return a.lenth<b.lenth;//按照路径长度排序 
}
int q[mx];//所有的询问 
int ans[mx];//询问是否成立 
int cnt;//当前路径数量 
void find(int u,int fa){//寻找当前树的重心 
    maxn[u]=0,size[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa||vis[v])continue;//防止回到已经找过的区域 
        find(v,u);
        size[u]+=size[v];
        maxn[u]=max(maxn[u],size[v]);
    }
    maxn[u]=max(maxn[u],s-size[u]);//可能往上是最大的子树 
    if(maxn[u]<maxn[root])root=u;//更新重心 
}
void get_dist(int u,int fa,int start){
    path[++cnt]=(Path){dist[u],start};
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa||vis[v])continue;
        dist[v]=dist[u]+edge[i].val;
        get_dist(v,u,start);
    }
}
void cal(int u){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        dist[v]=edge[i].val;
        get_dist(v,u,v);
    }
    sort(path+1,path+1+cnt,cmp);
    for(int i=1;i<=m;++i){//遍历所有询问 
        if(ans[i])continue;//其他子树中已经有该长度的路径了 
        for(int j=1;j<=cnt;++j){//先看看单条路径是否符合要求
            if(path[j].lenth==q[i]){
                ans[i]=1;
                break;
            }
        }
        if(ans[i])continue;//已经符合要求了就不用看两条路径相加了 
        int l=1,r=cnt;
        while(l<r){
            if(path[l].lenth+path[r].lenth<q[i])++l;//小了就左端点右移 
            else if(path[l].lenth+path[r].lenth>q[i])--r;//大了就右端点左移 
            else{
                if(path[l].from==path[r].from){//同一个子节点出发的路径不能相加
                    if(path[r].lenth==path[r-1].lenth)--r;
                    else if(path[l].lenth==path[l+1].lenth)++l;
                    else break; 
                }
                else{//找到了符合要求的路径 
                    ans[i]=1;
                    break;
                }
            }
        }
    }

}
void solve(int u){
    vis[u]=1;//标记已经找过 
    cnt=0;//清空no 
    cal(u);//以当前节点为重心计算一次 
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        s=size[v];
        root=0;
        maxn[0]=1<<30;//不能使0为重心 
        find(v,0);//找到子树的重心
        solve(root);//按照子树的重心重复操作 
    }
}
int main(){
//  freopen("in.txt","r",stdin);
    n=Read(),m=Read();
    for(int i=1;i<n;++i){
        int u=Read(),v=Read(),val=Read();
        add(u,v,val);
    }
    for(int i=1;i<=m;++i)q[i]=Read();
    maxn[0]=1<<30;//防止把0当成重心 
    find(1,0);//找初始重心 
    solve(root);
    for(int i=1;i<=m;++i)printf("%s\n",(ans[i]?"AYE":"NAY"));
    return 0;
}

这是一个A了的代码

两份代码唯一的差别就是solve函数中s的值不同，在T了的代码中，我的solve是这么写的：

void solve(int u){
    vis[u]=1;//标记已经找过 
    cnt=0;//清空no 
    cal(u);//以当前节点为重心计算一次 
    int ss=s;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        s=size[v];
        if(size[v]>size[u])s=ss-size[u];
        root=0;
        maxn[0]=1<<30;//不能使0为重心 
        find(v,0);//找到子树的重心
        solve(root);//按照子树的重心重复操作 
    }
}

而A了的代码中是这么写的：

void solve(int u){
    vis[u]=1;//标记已经找过 
    cnt=0;//清空no 
    cal(u);//以当前节点为重心计算一次 
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(vis[v])continue;
        s=size[v];
        root=0;
        maxn[0]=1<<30;//不能使0为重心 
        find(v,0);//找到子树的重心
        solve(root);//按照子树的重心重复操作 
    }
}

按照我的理解，A了的代码中找子树大小（即s)的写法应该是错的，因为如果v是u的父亲节点，s的值会出错，但是为什么这么写反而A了，另一种写法却会T呢？我看题解里很多都是按照A了的那种写法写的，但是不明白为什么，有没有好心的奆佬来帮帮忙啊

by 小粉兔 @ 2020-11-22 19:30:30

另一种写法 T 了是因为写错了

by 小粉兔 @ 2020-11-22 19:31:46

那个找子树大小错了的代码，确实错了。

但是分析一下发现还是对的，详见 https://liu-cheng-ao.blog.uoj.ac/blog/2969