點分治算法

澱粉質(點分治)

• 澱粉質(點分治)
• • • 一 定義
    • 二 前置芝士
    • • 1. 求樹的重心
      • 2. 求點到根的距離
      • 3. 求距離為k的點
      • 4. 求解從now為根的樹
    • 三 模版

澱粉質可真好吃

一 定義

 點分治是一種用于求在樹上的距離為 k k k 的點對的算法，如果暴力進行求解的話，時間的複雜度有 n 2 n^2 n2 ，很明顯對于這種時間複雜度會直接挂。

 我們可以知道在以 r o o t root root 為根的時候，那麼兩點之間的距離隻存在兩種情況

1. 經過root點
2. 不經過root點

 在經過 r o o t root root 的時候，我們可以枚舉已經經過的子樹中點的距離 a a a，在未經過的點到根的距離 b b b 中若有 a + b = k a + b = k a+b=k ,則 k k k 可行

在未經過 r o o t root root 的時候，直接判斷 a = = k a==k a==k 即可

 對于有根樹的話，那麼就不需要去求樹的重心，比較有根就沒有操作空間了，對于無根樹，那麼我們需要去取根，這個根為樹的重心的時候，可以使得需要向下遞歸的次數最少。

二 前置芝士

1. 求樹的重心

樹的重心指的是讓以此為根的時候，最大子樹的大小最小。求樹重心算法

void DFS(int now, int fa)
{
    size[now]=1; weight[now]=0;
    for(int i=head[now]; i; i=E[i].next)
    {
        int v=E[i].to;
        if(v == fa || vis[v]) continue;
        DFS(v, now);
        size[now]+=size[v];
        weight[now]=max(weight[now], size[v]);
    }
    weight[now]=max(weight[now], sum - size[now]);
    if(weight[now] < weight[ans]) ans=now;
}
           

2. 求點到根的距離

void get_dis(int now, int fa)
{
    disa[++disa[0]]=dis[now];
    for(int i=head[now]; i; i=E[i].next)
    {
        int v=E[i].to;
        if(v==fa||vis[v])continue; // vis的作用是将它限制在這個子樹裡
        dis[v]= dis[now] + E[i].dis;
        get_dis(v, now); // 繼續搜尋子節點
    }
}
           

3. 求距離為k的點

void get_ndis(int u)
{
    int p=0;
    for(int i=head[u];i;i=E[i].next)
    {
        int to=E[i].to;
        if(vis[to])continue;
        disa[0]=0; dis[to]=E[i].dis;
        get_dis(to, u); // 進行預處理
        for(int j=disa[0]; j; --j)
            for(int k=1;k<=m;++k)
                if(ask[k] >= disa[j])
                    test[k]|=mark[ask[k] - disa[j]];
      // 查找路徑之和為ask[k]的兩點
        for(int j=disa[0]; j; --j)
            q[++p]=disa[j], mark[disa[j]]=1;
    }
    for(int i=1;i<=p;++i)
        mark[q[i]]=0;

}
           

4. 求解從now為根的樹

void solve(int now)
{
    vis[now]= mark[0]=1;
    get_ndis(now);
    for(int i=head[now]; i; i=E[i].next)
    {
        int v=E[i].to;
        if(vis[v])continue;
        sum=size[v]; weight[ans=0]=inf;
        DFS(v, 0); solve(ans);
    }
}
           

三 模版

模版題澱粉質