点分治学习笔记

一.理解：

点分治，运用了分而治之的思想，每次算出根及不同子树之间的贡献，再将每棵子树看作一棵新的树，以重心为根继续递归。
其好处主要是将递归层数限制在\(O(log_{2}n)\)下，且每次最多不会遍历超过n个点，使总时间在\(O(log_{2}n)\)下。

二.操作：

1.找重心:(分为get_size()[可以不做]和find_root()两部分)
2.算贡献:(get_ans())
3.继续递归。

三.代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10006,maxn=1e7+1;
int n,m,t1,t2,t3,rt=0,cnt=0,ans=0,sum,v[N],head[N],siz[N];
int judge[maxn],dis[N],q[N],ask[N],task[N],num[N],maxp[N];
struct edge{int nxt,to,w;}e[N<<1];
inline void add(int u,int v,int w){e[++cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt;}
inline int read(){
    int T=0,F=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') F=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
    return F*T;
}
void find_root(int x,int fa){
    siz[x]=1,maxp[x]=0;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa){
            find_root(e[i].to,x);
            siz[x]+=siz[e[i].to];
            maxp[x]=max(maxp[x],siz[e[i].to]);
        } 
    maxp[x]=max(maxp[x],sum-siz[x]);
    if(maxp[rt]>maxp[x]) rt=x;
}
void get_dis(int x,int fa){
     q[++q[0]]=dis[x];
     for(int i=head[x];i;i=e[i].nxt)
        if(!v[e[i].to]&&e[i].to!=fa){
            dis[e[i].to]=dis[x]+e[i].w;
            get_dis(e[i].to,x);
        }
}
void get_ans(int x){
    num[0]=0;
    for(int i=head[x];i;i=e[i].nxt)
        if(!v[e[i].to]){
            dis[e[i].to]=e[i].w,q[0]=0,get_dis(e[i].to,x);
            for(int j=1;j<=q[0];++j) for(int k=1;k<=m;++k) if(ask[k]>=q[j]) task[k]|=judge[ask[k]-q[j]];
            for(int j=1;j<=q[0];++j) num[++num[0]]=q[j],judge[q[j]]=1;
        }
    for(int i=1;i<=num[0];++i) judge[num[i]]=0;
}
void work(int x){
    v[x]=1,judge[0]=1,get_ans(x);
    for(int i=head[x];i;i=e[i].nxt)
        if(!v[e[i].to]){
            sum=siz[e[i].to],rt=0;
            find_root(e[i].to,x);
            work(e[i].to);
        }
}
int main(){
    maxp[0]=maxn;
    n=read(),m=read();
    for(int i=1;i<n;++i) t1=read(),t2=read(),t3=read(),add(t1,t2,t3),add(t2,t1,t3);
    for(int i=1;i<=m;++i) ask[i]=read();
    sum=n,find_root(1,0),work(rt);
    for(int i=1;i<=m;++i){
        if(task[i]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}

点分治学习笔记

原文：https://www.cnblogs.com/ljk123-de-bo-ke/p/11434404.html