HDU 6686 Rikka with Travels 树的直径

旧城等待， 2023-08-17 17:22 105阅读 0赞

题意：定义两点之间的距离为从一个点到另一个点经过的点数之和（包括这两个点），设二元组(x, y)为两条不相交的路径，一条长度为x，一条长度为y，问二元组（x, y）出现了多少次？

思路：直接上jls的讲解：

基础直径练习题。  
考虑判断 能不能出现。劼论：任意取树上的一条直径，那么如果 能出现，那么一定存在一 种方案使得直径的两端都被使用了。证明很简单：假设存在一个端点没有被使用，那么考虑两条直线的 四个端点 ，一定可以把一个端点给移动到直径的这个端点上，因为直径是树上长的路径，因 此这次移动一定不会减少路径的长度。  
考虑对每一个长度 ，求可以满足的长的 ，这样所有小于等于 的值也都能被满足。考虑在直径上 计算这些值：第一种情况，直径的两端分属不同的路径，那么可以枚举直径的一个端点那条路径在直径 上的后一个点，那么这一条路径的大长度就是这个点到直径端点的距离加上这个点往直径外的大 延伸长度，另一条路径的大长度也可以类似地求，其中大延伸长度可以用一个 的 DFS 计算出 来。第二种情况是有一条路径就是这条直径，那么另一条路径就是这条直径之外的长路径长度，这个 只要把直径上的点都删了再求一遍直径就行。  
总的时间复杂度为 O(n)。

代码：

#include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    const int maxn = 100010;
    vector<int> G[maxn];
    int mp[maxn], mx_dis[maxn], f[maxn],Mx[maxn];
    bool v[maxn], v1[maxn];
    int root, mx, now;
    vector<int> a;
    void add(int x, int y) {
        G[x].push_back(y);
        G[y].push_back(x);
    }
    void dfs(int x, int fa, int dis, bool flag) {
        f[x] = fa;
        v1[x] = flag;
        if(dis > mx) {
            mx = dis;
            now = x;
        } 
        for (auto y : G[x]) {
            if(y == fa || v[y]) continue;
            dfs(y, x, dis + 1, flag);
        }
    }
    int dfs1(int x, int fa) {
        int mx = 0;
        for (auto y : G[x]) {
            if(v[y] || y == fa) continue;
            mx = max(mx, dfs1(y, x));
        }
        return mx + 1;
    }
    int main() {
        int T, x, y, n;
    //    freopen("6686in.txt", "r", stdin);
    //    freopen("out1.txt", "w", stdout);
        scanf("%d", &T);
        while(T--) {
            scanf("%d", &n);
            a.clear();
            for (int i = 1; i <= n; i++)
                G[i].clear();
            for (int i = 1; i < n; i++) {
                scanf("%d%d", &x, &y);
                add(x, y); 
            }
            for (int i = 1; i <= n; i++) 
                v[i] = v1[i] = mp[i] = f[i] = mx_dis[i] = 0;
            root = 1, mx = 0;
            dfs(root, 0, 1, 0);
            root = now, mx = 0;
            dfs(root, 0, 1, 0);
            for (int i = now; i; i = f[i]) {
                v[i] = 1;
                a.push_back(i);
            }
            for (auto x : a) {
                mx_dis[x] = dfs1(x, 0);
            }
            for (int i = 1; i <= n; i++) v1[i] = 0;
            int tmp = 0;
            for (int i = 1; i <= n; i++) {
                if(v[i] == 0 && v1[i] == 0) {
                    now = mx = 0;
                    dfs(i, 0, 1, 0);
                    dfs(now, 0, 1, 1);
                    tmp = max(tmp, mx);
                }
            }
            mp[a.size()] = tmp;
            mp[tmp] = a.size();
            Mx[a.size()] = 0;
            for (int i = a.size() - 2; i >= 0; i--) {
            	Mx[i + 1] = max(Mx[i + 2], (int)a.size() - i - 2 + mx_dis[a[i + 1]]);
    		}
            for (int i = 0; i < a.size() - 1; i++) {
                int x = i + mx_dis[a[i]];
                int y = Mx[i + 1];
                mp[x] = max(mp[x], y);
                mp[y] = max(mp[y], x);
            }
            LL ans = 0;
            mx = 0;
            for (int i = a.size(); i >= 1; i--) {
                mx = max(mx, mp[i]);
                ans += mx;
            }
            printf("%lld\n", ans);
        }        
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11407720.html