点分治

例题

题目描述

给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。

输入格式

第一行两个数 $n,m$。

第 $2$ 到第 $n$ 行，每行三个整数 $u, v, w$，代表树上存在一条连接 $u$ 和 $v$ 边权为 $w$ 的路径。

接下来 $m$ 行，每行一个整数 $k$，代表一次询问。

输出格式

对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。

样例 #1

样例输入 #1

2 1
1 2 2
2

样例输出 #1

AYE

数据规模与约定

• 对于 $30%$ 的数据，保证 $n\leq 100$。
• 对于 $60%$ 的数据，保证 $n\leq 1000$，$m\leq 50$ 。
• 对于 $100%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。

• 算法分析
• 模板

基本思想

点分治，顾名思义就是基于树上的节点进行分治。
如果我们在深入一点呢？对于点的拆开其实就是对于树的拆开。
所以我认为点分治的本质其实是将一棵树拆分成许多棵子树处理，并不断进行。
这应该也是点分治的精髓。
既然我们要将一个点进行分治，那么选点肯定最首要的。
思考下面一个问题：
如果树退化为一个链，
我们选取链首作为分治点，理论时间复杂度？
而如果选择链的中心，它的理论时间复杂度又是多少？
选择链首：$O(n)$
选择链心：$O(\log n)$
通过这个例子,我们不难发现：
如果选点后左右子树越大，递归层数越多，时间越慢，反之则越快。
所以我们的选点标准就出来了，而我们把有这个性质的点叫做：树的重心！

求解树的重心

void getroot(int now,int fa){
    tree[now].size=1,tree[now].mx=0; //初始化当前树
    for(auto i : tree[now].to){  //遍历每棵子树
        if(i.to==fa || tree[i.to].usd) continue; //特判，防止死循环
        getroot(i.to,now); //递归查找根
        tree[now].size+=tree[i.to].size; //重新计算子树大小
        tree[now].mx=max(tree[now].mx,tree[i.to].size); //找出最大子树
    }
    tree[now].mx=max(tree[now].mx,tree[0].mx-tree[now].size); 
    /*此处 tree[0].mx-tree[now].size
    因为父节点也有大小；因此要将父节点算入
    */
    if(tree[now].mx<tree[root].mx) root=now; //优化选根
}

分治中心算法

void divid(int now){
    calc(now);
    tree[now].usd=true;
    for(auto i : tree[now].to){
        if(!tree[i.to].usd){
            root=0;
            tree[0].mx=tree[i.to].size;
            getroot(i.to,0),getroot(root,0);
            divid(root);
        }
    }
}

#include<iostream>
#include <vector>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
int n,m,d[26005],hav[10000005],cnt=0;
int ans[26005];
struct ro{
    int to;
    int val;
};
struct node{
    vector <ro> to;
    int size;
    int dis;
    int mx;
    bool usd;

}tree[50005];
int root;
void getroot(int now,int fa){
    tree[now].size=1,tree[now].mx=0;
    for(auto i : tree[now].to){
        if(i.to==fa || tree[i.to].usd) continue;
        getroot(i.to,now);
        tree[now].size+=tree[i.to].size;
        tree[now].mx=max(tree[now].mx,tree[i.to].size);
    }
    tree[now].mx=max(tree[now].mx,tree[0].mx-tree[now].size);
    if(tree[now].mx<tree[root].mx) root=now;
}

void getdis(int now,int fa){
    d[++cnt]=tree[now].dis;
    for(auto i : tree[now].to){
        if(i.to==fa||tree[i.to].usd) continue;
        tree[i.to].dis=tree[now].dis+i.val;
        getdis(i.to,now);
    }
}

void calc(int now){
    hav[0]=1;
    vector<int>v;
    for(auto i : tree[now].to){
        if(tree[i.to].usd)continue;
        cnt=0;
        tree[i.to].dis=i.val;
        getdis(i.to,now);
        for(int j = 1;j<=cnt;j++){
            for(int k = 1;k<=m;k++){
                if(k>=d[j]) ans[k] |=hav[k-d[j]];
            }
        }
        for(int j = 1;j<=cnt;j++){
            if(d[j]<=1e7){
                hav[d[j]] =1;
                v.push_back(d[j]);
            }
        }
    }

    for(auto i:v){
        hav[i]=0;
    }
}
void divid(int now){
    calc(now);
    tree[now].usd=true;
    for(auto i : tree[now].to){
        if(!tree[i.to].usd){
            root=0;
            tree[0].mx=tree[i.to].size;
            getroot(i.to,0),getroot(root,0);
            divid(root);
        }
    }
}
int main(){
    n=read();
    int u,v,w;
    for(int i = 1;i<n;i++){
        u=read(),v=read(),w=read();
        tree[u].to.push_back((ro){v,w});
        tree[v].to.push_back((ro){u,w});
    }
    m=read();
    tree[0].mx=n;
    getroot(1,0),getroot(root,0);
    divid(root);
    long long sum=0;
    for(int i = 1;i<=m;i++) sum+=ans[i];
    cout<<sum;
    return 0;
}