树的直径

定义

  • 树中所有最短路径距离的最大值即为树的直径

求法

  1. 首先在树上任取一点u, 记录距离u最远的节点为d1, d1即为树直径的端点之一
  2. 寻找距离d1最远的节点d2
  3. d1d2的路径即为树的直径
  • 可以使用两次dfs搜索答案
// vector G[v];
void dfs(int in){
    vis[in] = 1;
    for(auto e : G[in]){
        if(!vis[in]){
            dis[e.v] = dis[in] + e.w;
            if(dis[e.v] > maxdis){
                maxdis = dis[e.v];
                maxpoint = e.v;
            }
        }
        dfs(e.v);
    }
}

拓展

  • 利用树的直径可以在O(n)的求出每个结点的最远点
  • 可以证明的是 :
    • 一个点的最远点一定在树的直径的端点上
  • 所以利用进行三次dfs即可求出树上最远点
void dfs(int in, int mark){
    vis[in] = 1;
    for(auto e : G[in]){
        if(!vis[in]){
            dis[e.v][mark] = dis[in][mark] + e.w;
            if(dis[e.v] > maxdis){
                maxdis = dis[e.v][mark];
                maxpoint = e.v;
            }
        }
        dfs(e.v);
    }
}

int main(){
    dfs(root, 0); //找第一个端点
    dfs(d1, 0); // 找第二个端点的同时记录所有点与d1的距离
    dfs(d2, 1); // 记录所有点与d2的距离
    // max(dis[i][0], dis[i][1]) 即为所求
}

例题

世界上一共有n个国家,标号从1∼n。他们由n−1条边连接着,经过每条边都有一定的时间花费。任意两个国家之间两两可达。火山哥一共决定去K个国家。现在他想要知道:如果他从第i个国家出发,经过这K个国家的最短时间是多少?

第一行两个整数n,K,题意如题面所述。

接下来n−1行,每行三个整数u,v,w,表示存在一条从u到v长度为w的边。

接下来K行,每行一个整数,表示火山哥想去的某个国家,保证这K个国家两两不同。

// Wqr_
// Time : 20/01/16
#include <bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ddd(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ttt cerr<<"test"<<endl
typedef long long ll;
using namespace std;
#define int long long
const int N = 5e5 + 50;
struct edge {
    int v, w;
};
vector<edge> G[N];
bool ifk[N];
int f[N], fk[N], dis2k[N], disk2k[N][2];
int n, k;
void build_tree(int in){
    for(auto e : G[in]){
        if(e.v != f[in]){
            f[e.v] = in;
            build_tree(e.v);
        }
    }
}
void build_K_tree(){
    for(int i = 1; i <= n; i++){
        if(ifk[i]){
            int tmp = i;
            while(!ifk[f[tmp]] && f[tmp]){
                tmp = f[tmp];
                ifk[tmp] = 1;
                k++;
            }
        }
    }
}
int sizek;
void getsizek(int in){
    for(auto e : G[in]){
        if(e.v != f[in] && ifk[e.v]){
            sizek += e.w;
            getsizek(e.v);
        }
    }
}
void getdis2k(int in, int lastk){
    if (ifk[in]) dis2k[in] = 0, lastk = in;
    fk[in] = lastk;
    for(auto e : G[in]){
        if(e.v != f[in]){
            dis2k[e.v] = dis2k[in] + e.w;
            getdis2k(e.v, lastk);
        }
    }
}
int maxdisk2k, maxpoint, vis[N];
void getdisk2k(int in, int mark){
    vis[in] = 1;
    for(auto e : G[in]){
        if(!vis[e.v] && ifk[e.v]){
            disk2k[e.v][mark] = disk2k[in][mark] + e.w;
            if(disk2k[e.v][mark] > maxdisk2k){
                maxdisk2k = disk2k[e.v][mark];
                maxpoint = e.v;
            }
            getdisk2k(e.v, mark);
        }
    }
}
signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    int u, v, w;
    for(int i = 0; i < n-1; i++){
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for(int i = 0; i < k; i++){
        cin >> u;
        ifk[u] = 1;
    }
    build_tree(u);
    build_K_tree();
    getsizek(u);
    getdis2k(u, u);
    int d1, d2;

    maxdisk2k = maxpoint = 0;
    memset(vis, 0, sizeof(vis));
    getdisk2k(u, 0);
    d1 = maxpoint;

    maxdisk2k = maxpoint = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++){
        disk2k[i][0] = 0;
    }
    getdisk2k(d1, 0);
    d2 = maxpoint;

    maxdisk2k = maxpoint = 0;
    memset(vis, 0, sizeof(vis));
    getdisk2k(d2, 1);
    for(int i = 1; i <= n; i++){
        int ans = dis2k[i] + sizek * 2 - max(disk2k[fk[i]][0], disk2k[fk[i]][1]);
        cout << ans << endl;
    }
    return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

domjudge docker 部署并部署远程判题机 上一篇
[模板]-树链剖分 下一篇