Codeforces 87D Beautiful Road
Description
给定一个无向图，\(n\) 个点，\(n-1\) 条边，保证图联通（就是一棵树），并且给定每条边的权值。任取两个点，连接二者的路径上权值最大的边（可以不止一条）的魅力值+2。求边的最大魅力值，以及该魅力值对应的所有边。
Solution
先考虑两种特殊情况：
（1）若所有的边权值都相等：对于每条边，假设它的两边连接的点数分别为 \(x,y\) ，则该边的魅力值为 \(x*y*2\)。只需要建立一棵树，遍历一遍统计已任意结点为根的子树结点数，便可计算所有边的魅力值，从而得出答案。（若以\(rt1\)为根的子树大小为\(m\)，则连接\(rt1\)和它的父结点的边的魅力值为 \(m*(n-m)\) ）
（2）若所有边权值都不等：考虑按照权值从小到大地向图中加入边，用并查集维护联通性，当加入第 \(i\) 条边时，将加入它之前两个顶点所在地并查集大小相乘（再乘上\(2\)）便可得到该边魅力值。将所有边加入后，也就得到了答案。
在本题中，对边的权值没有限制，也就是说既有不同的也有相同的。所以，如果直接应用上述\((2)\)中的方法是不对的。可以想到，应该按照权值从小到大，但是一次不是只加入一条边，而是应该加入权值相等的所有边，然后统计这些边的答案，再进行下一轮加边。
那么现在的问题就是，在一次性加入相等权值的边之后如何统计这些边的魅力值。在上述\((2)\)中，统计边的答案是在加边之前，但是现在必须是在加边之后。考虑能否确定一种在权值相等时边的加入顺序，使得在加入这些边之后，边的某个端点连接点数不会改变。
以任意点为根建一棵树，将相等的边按照由深到浅的顺序加入，这样一来，边连接的更深的点所连的结点数（或者说，并查集大小，或者说，当前子树大小）是不会改变的，在加入边之前记录这个值，等所有同等权值的边加入后，就可以利用前面临时记录的值和边所在的并查集总大小统计答案了。（感觉说得有点抽象，可以自己想象一下 \(qwq\)）
Code
//by DTTTTTTT 2023.3.14
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 5; //当然不能只写1e5啦
int n, fa[N], Size[N], dep[N], tmp[N];
vector<int>to[N];
ll val[N];
struct edge {
int u, v, id, dep;
ll w;
}e[N];
bool cmp(edge x,edge y){
if (x.w == y.w)
return x.dep > y.dep;
return x.w < y.w;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void join(int i, int u, int v) {
int fu = find(u), fv = find(v);
tmp[i] = Size[fv];
fa[fu] = fv;
Size[fv] += Size[fu];
}
void dfs(int u, int fa, int depp) {
dep[u] = depp;
for (int i = 0;i < to[u].size();++i) {
int v = to[u][i];
if (v == fa) continue;
dfs(v, u, depp + 1);
}
}
int main() {
cin >> n;
for (int i = 1;i < n;++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].id = i;
to[e[i].u].push_back(e[i].v);
to[e[i].v].push_back(e[i].u); //这一步写错结果debug半天，，
}
for (int i = 1;i <= n;++i)
fa[i] = i, Size[i] = 1;
dfs(1, 0, 0);
for (int i = 1;i < n;++i) {
if (dep[e[i].u] > dep[e[i].v])
swap(e[i].u, e[i].v); //e[i].v是更深的点
e[i].dep = dep[e[i].v];
}
sort(e + 1, e + n, cmp);
int num = 0;
for (int i = 1;i < n;++i) {
int u = e[i].u, v = e[i].v, w = e[i].w;
join(i, u, v), ++num;
if (i == n - 1 || w != e[i + 1].w) {
for (int j = i - num + 1;j <= i;++j)
val[e[j].id] = 1ll * tmp[j] * (Size[find(e[j].u)] - tmp[j]) * 2;
num = 0;
}
}
num = 0;
ll maxval = 0; //写ll！！！
for (int i = 1;i < n;++i)
if (maxval < val[i])
maxval = val[i], num = 1;
else if (maxval == val[i])
++num;
cout << maxval << " " << num << endl;
for (int i = 1;i < n;++i)
if (maxval == val[i])
cout << i << " ";
return 0;
}