Codeforces Round 1000 (Div. 2)-C题(树上两个节点不同边数最大值)

https://codeforces.com/contest/2063/problem/C
牢记一棵树上两个节点如果相邻,它们有一条边会重叠,两个节点延伸出去的所有不同边是两个节点入度之和-1而不是入度之和,那么如果这棵树上有三个节点它们的入度都相同,那么优先选择非相邻的两个节点才能使所有不同边的数量最大!!

然后思路就是:暴力

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << (int)std::log2(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info& v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        }
        else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info& v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

struct Info {
    int max=0;
};
Info operator+(Info a, Info b) {
    return { std::max(a.max,b.max) };
}


void solve() {
    int n;
    std::cin >> n;
    std::vector<Info>a(n);
    std::vector<std::vector<int>>adj(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        a[u].max++;
        a[v].max++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    SegmentTree<Info>t(a);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        t.modify(i, { 0 });
        for (int j = 0; j < adj[i].size(); j++) {
            int x = adj[i][j];
            t.modify(x, { a[x].max - 1 });
        }
        ans = std::max(ans, a[i].max + t.rangeQuery(0, n).max);
        t.modify(i, { a[i]});
        for (int j = 0; j < adj[i].size(); j++) {
            int x = adj[i][j];
            t.modify(x, { a[x].max });
        }
    }
    std::cout << ans-1 << "\n";
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/Colinnian/article/details/145311828

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！