87-D 题目大意
给定一颗\(n\)个节点的树，边带权。
现在要枚举所有路径，对于一条路径，取边权最大的边给它得分加\(1\)；若有多个权最大的边，则这些边的得分都加\(1\)。
输出最后所有边中的最大的得分是多少，有多少条得分最大的边。第二行输出这些得分最大的边的编号
Solution
首先考虑简化版，如果边权都不一样怎么做。
对于这样的经典模型，通用的做法是对边进行排序，按边权从小到大枚举边，这条边的得分为它连接的两个联通块的大小之积，计算之后用并查集合并两个连通块。
现在的问题中存在权值相同的边权，显然我们每次枚举需要把权值相同的边统一处理了，难点在于计算得分策略的设计。
枚举一组权值相同的边，设一个边\(e\)连接的两个端点\(u,v\)（其中\(dep[u]>dep[v]\)），我们记录下每条边连接的\(u\)所对应的连通块的大小\(siz[u]\)，然后在并查集中把这些边全部进行合并，之后再次枚举这些边计算贡献，则此时能够计算出边\(e\)的得分为\((siz[u']-siz[u])*siz[u]*2\)（其中\(u'\)表示并查集合并之后的\(u\)点）
基于这样的想法，显然我们需要保证后续的合并不会影响前面所有的\(u\)所在的连通块大小。因为能够影响到\(u\)所在连通块大小的其他连通块一定比它深度更大。所以这里我们对同组的边按深度进行排序，优先处理深度更大的边。
时间复杂度\(O(nlogn+n·α(n))\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
struct DSU{
int n;
vector<T> p,siz;
DSU(int _n):p(_n+1),siz(_n+1),n(_n){
iota(p.begin(),p.end(),0);
for(int i=0;i<=n;i++) siz[i]=1;
}
T findd(T x){
return p[x]==x?x:p[x]=findd(p[x]);
}
void unionn(T x,T y){
x=findd(x),y=findd(y);
if(x==y) return;
if(siz[x]>siz[y]) swap(x,y);
p[x]=y;
siz[y]+=siz[x];
}
};
void solve(){
int n;
cin>>n;
vector<vector<pair<int,int>>> g(n);
vector<array<int,4>> e(n-1);
for(int i=0;i<n-1;i++){
int x,y,w;
cin>>x>>y>>w;
x--,y--;
e[i]={x,y,w,i};
g[x].push_back({y,w});
g[y].push_back({x,w});
}
vector<int> dep(n);
function<void(int,int,int)> dfs=[&](int x,int fa,int depth){
dep[x]=depth;
for(auto t:g[x]){
if(t.first==fa) continue;
dfs(t.first,x,depth+1);
}
};
dfs(0,-1,0);
sort(e.begin(),e.end(),[&](const auto &a,const auto &b){
int x1=a[0],y1=a[1],x2=b[0],y2=b[1];
return a[2]==b[2]?max(dep[x1],dep[y1])>max(dep[x2],dep[y2]):a[2]<b[2];
});
DSU<int> dsu(n);
ll ans=0;
int cnt=0;
vector<ll> res(n-1);
for(int i=0;i<n-1;){
int x=e[i][0],y=e[i][1];
queue<int> q;
int j=i;
while(j<n-1&&e[j][2]==e[i][2]){
if(dep[e[j][0]]<dep[e[j][1]]) swap(e[j][0],e[j][1]);
q.push(dsu.siz[dsu.findd(e[j][0])]);
dsu.unionn(e[j][0],e[j][1]);
j++;
}
while(i<j){
res[e[i][3]]=1LL*q.front()*(dsu.siz[dsu.findd(e[i][0])]-q.front())*2;
if(res[e[i][3]]>ans){
ans=res[e[i][3]];
cnt=1;
}else if(res[e[i][3]]==ans){
cnt++;
}
q.pop();
i++;
}
}
cout<<ans<<" "<<cnt<<'\n';
for(int i=0;i<n-1;i++){
if(res[i]==ans) cout<<i+1<<" ";
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}