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;
}