点分治のテーマ

点分治詳細解析
【点分治】の学習ノートと多くの例題
P 3806【テンプレート】点分治1
木の上で最小の距離がKの点の対が存在するかどうかを求めます
オフライン+ポイント分割
問題解

#include
using namespace std;
const int MAX=1e4+5;
const int INF=1e7;
int n,m,K;
struct P
{
    int to,nxt,v;
    void is(int x1,int x2,int x3){to=x1;nxt=x2;v=x3;}
}e[MAX<<1];
int head[MAX],sz[MAX],dis[MAX],maxp[MAX],rem[MAX],test[MAX],query[MAX],judge[INF],q[MAX],cnt,sum,rt;
bool vis[MAX];
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}
void adde(int u,int v,int w)
{
    e[cnt].is(v,head[u],w);head[u]=cnt++;
    e[cnt].is(u,head[v],w);head[v]=cnt++;
}
void getrt(int u,int pa)
{
    sz[u]=1; maxp[u]=0;
    for(int i=head[u];i!=-1;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==pa||vis[to]) continue;
        getrt(to,u);
        sz[u]+=sz[to];//update the number of subnode in root [u],[to] is [u]‘s subnode
        maxp[u]=max(maxp[u],sz[to]);//update the max of root [u],if sz [to] is greater
    }
    maxp[u]=max(maxp[u],sum-sz[u]);//in_ex
    if(maxp[u]=rem[j])
        test[k]|=judge[query[k]-rem[j]];
        // query[k]-rem[j]d k 
        for(int j=rem[0];j;--j)// dis judge
        q[++p]=rem[j],judge[rem[j]]=1;
    }
    for(int i=1;i<=p;++i)// judge
    judge[q[i]]=0;// memeset， T
}
void divide(int u)
{
    //judge[i] i 
    vis[u]=1;judge[0]=1; calc(u);// u 
    for(int i=head[u];i!=-1;i=e[i].nxt)// 
    {
        int to=e[i].to;
        if(vis[to])continue;
        sum=sz[to]; maxp[rt=0]=INF;
        getrt(to,0); divide(rt);// 
    }
}
int main()
{
    int x,y,z;
    init();
    scanf("%d%d",&n,&m);
    for(int i=1;i

POJ1741 Tree
木の上で最小の距離がmの点の対の個数より小さいことを求めます

#include
#include
#include
using namespace std;
const int MAX=1e4+5;
int n,m;
struct P
{
    int to,nxt,v;
    void is(int x1,int x2,int x3){to=x1;nxt=x2;v=x3;}
}e[MAX<<1];
int head[MAX],sz[MAX],dis[MAX],maxp[MAX],rem[MAX],cnt,sum,rt,ans;
bool vis[MAX];
void init()
{
    cnt=ans=rt=0;rem[0]=0;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
}
void adde(int u,int v,int w)
{
    e[cnt].is(v,head[u],w);head[u]=cnt++;
    e[cnt].is(u,head[v],w);head[v]=cnt++;
}
void getrt(int u,int pa)
{
    sz[u]=1; maxp[u]=0;
    for(int i=head[u];i!=-1;i=e[i].nxt)
    {
        int to=e[i].to;
        if(to==pa||vis[to]) continue;
        getrt(to,u);
        sz[u]+=sz[to];//update the number of subnode in root [u],[to] is [u]‘s subnode
        maxp[u]=max(maxp[u],sz[to]);//update the max of root [u],if sz [to] is greater
    }
    maxp[u]=max(maxp[u],sum-sz[u]);//in_ex
    if(maxp[u]

点対の最小距離がmの数量に等しいことを求めます

int cal_(int u,int ct)
{
    dis[u]=ct;rem[0]=0;
    getdis(u,0);
    sort(rem+1,rem+rem[0]+1);
    int r=rem[0],x=0;
    for(int l=1;l