http://codevs.cn/problem/1188/ 我靠我不会； fop_zz教我了半天我才会的； 首先n*n的暴力就是每条线段从两个点dfs； 然后把两个点的值乘起来*2； 这就是一条的值了； 我们在考虑权值不同的情况； 我们只要把边从小到大排序然后用并查集维护就好了； 但是如果边权有相同的情况就不好搞了；
有一个想法； 就是我们同一个权值的边一起加； 对于一条边，加之前其一段的点数是a，加之后是总共点数b； 那么值就是(b-a)*a*2; 这就有问题了，我们并查集不可以存点数了； 因为并查集在不断变化； 那我们只好把点数存在点上了； 这个时候我们要先搞一个dfs树； 记录每个节点的深度； 而并查集维护的就是这个联通快的点数放在哪里； 其实全放在联通快深度最高点； 我们合并两个并查集的时候，就要把低节点合并到高节点去； 比如x-y这一线段 x深度浅 那么get(y)一定是y 我们要把 fa[y]=get(x) 并且把点数合并过去； 于是y~get(x)的点的点数全要加x的点数； 因为我们要计算答案的； 仅仅把get(x)的权值加上y是不够的；
#include<bits/stdc++.h> #define Ll long long using namespace std; const int N=1e5+5; struct cs{int v,to,nxt;}a[N*2]; struct in{int x,y,z,num;}I[N]; struct dian{int deep,fa,size;}d[N]; int fa[N]; int head[N],ll; int an[N],top; Ll ans; int n,m,l,r,x,y,z; void init(int x,int y,int z){ a[++ll].to=y; a[ll].v=z; a[ll].nxt=head[x]; head[x]=ll; } void dfs(int x,int y,int z){ d[x].deep=z; d[x].fa=y; d[x].size=1; fa[x]=x; for(int k=head[x];k;k=a[k].nxt) if(a[k].to!=y)dfs(a[k].to,x,z+1); } bool cmp(in a,in b){return a.z<b.z;} int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} void insert(int x,int y){ int yy=get(y); fa[x]=yy; for(int k=d[x].fa;k!=yy;k=d[k].fa)d[k].size+=d[x].size; d[yy].size+=d[x].size; } int main() { freopen("City.in","r",stdin); freopen("City.out","w",stdout); scanf("%d",&n);n--; for(int i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); I[i].x=x; I[i].y=y; I[i].z=z; I[i].num=i; init(x,y,z);init(y,x,z); } dfs(1,-1,1); sort(I+1,I+n+1,cmp); l=1;r=1; while(l<=n){ while(r+1<=n&&I[r+1].z==I[r].z)r++; for(int i=l;i<=r;i++){ x=I[i].x; y=I[i].y; if(d[x].deep>d[y].deep)insert(x,y);else insert(y,x); } for(int i=l;i<=r;i++){ x=I[i].x; y=I[i].y; if(d[x].deep>d[y].deep){ y=d[get(y)].size; x=d[x].size; }else{ y=d[y].size; x=d[get(x)].size; swap(x,y); } Ll temp=(Ll)(y-x)*x; if(ans==temp)an[++top]=I[i].num; if(ans<temp)ans=temp,an[top=1]=I[i].num; } l=r+1;r=l; } sort(an+1,an+top+1); printf("%lld %d\n",ans*2,top); for(int i=1;i<=top;i++)printf("%d ",an[i]); }其实这种写法会被卡掉； 我们搞一条链的话
for(int k=d[x].fa;k!=yy;k=d[k].fa)d[k].size+=d[x].size;这里会萎； 但是如果我们把同权值的线段先排序； 这就好啦
