世界真的很大 今天考试时做了这道题，当时有点思路但是完全不敢写 还是要有勇于尝试的勇气，写着写着可能就写出来了 不要畏惧于去想，大多数情况下最后的代码都比想象的要简单 对于熟悉的问题要灵活掌握其性质，对于题目要敢于分析题目的独有性质 但是一定要仔细看题先：
一下午的思考后，思路什么的还是比较明确了，先总结如下 首先题目很明确的要求了最小生成树，那么我们不管三七二十一，先求一颗最小生成树再说 那么就得到了两类边，一类是在最小生成树上的边，一类是不在最小生成树上的边
对于前者，我们想要知道可以使其一直留在最小生成树上的最大边权，对于后者，我们想要知道可以使其跻身最小生成树的最大边权 先考虑后者
对于一条不在最小生成树上的边，要想让它到最小生成树上，而树上两点之间的路径是唯一的，这条边的左右两点就会连通，就意味着之前最小生成树上使得这两条边连通的路径上的一条边会被挤下去，那么那条边会被挤下去呢，当然是里面边权最大的那条边了， 所以只要这条现在不在最小生成树上的边的权值变得比那条路径上权值最大的边权值小1，就能把他挤下去，而两点之间又必须连通，另一条路上被挤下去了一条，断了，所以这条边就断不开了，一定会出现在任意一个最小生成树上 也就是说，对于一条不在最小生成树上的边，其最大的权值就是最小生成树上使得这条边两端点连通的路径上边权最大的那条边的权值减一
对于前者，也就是在最小生成树上的一条边，考虑要想使得其从最小生成树上被挤下去，首先就是要使得由于这条边断开，左右两端点通过新的路径重新连通 而由于重新连通是需要新的边的而只所以这条边会被替代，只可能因为原本的边的边权比新的边的边权大，才会被替代 也就是说，要想这条边永远留在最小生成树上，就需要其值比所有能使得其左右两端在其断开后重新连通的边的值都要小，就是这些边的最小值减一
对于第一种情况，换句话说就是在最小生成树上求一条链的最值，可以用倍增来解决
对于第二种情况，枚举所有在最小生成树上的边，再去找所有能使得其左右两点重新连通的不在最小生成树上的边显然不现实，换个思路考虑，每条不在不在最小生成树上的边可以更新答案的范围，就是其左右两点在最小生成树上的一条链，相当于每次更新就是对于一条链上的答案全部对其取个min值，而这是树上的路径维护问题，显然可以用树链剖分的方法来做
现在已经是这道题的正解了，复杂度nlogn，但还不够 树链剖分在套个线段树，写起来。。。
最小生成树的性质几乎已经分析够了，但是对于这道题目单独而言，还有更有效率的解法
考虑第一种情况，我们是枚举所有不在最小生成树上的边，而第二种情况，本来是枚举所有在最小生成树上的边，转化之后也变成了枚举所有不在最小生成树上的边了，好像可以一起搞定 考虑第一次查询的范围，是枚举的边左右两点在最小生成树上的一条链，而第二次更新的范围也是左右两点的一条链 范围的相同更加印证了两种情况可以一起来讨论了 现在对于每次更新的范围和查询范围相同，依然可以用树链剖分来搞定
现在考虑，查询自不用说，复杂度非常优美，考虑更新，有没有比起树链剖分更好写，但是同样高效的方法 查询是用的倍增，显然更新没办法像倍增一样跳着跳着地更新，所以必然是其他方法 考虑每次更新是取的min值，就是说，如果一条链已经被一条边更新了，再被另一条边权较大的边更新，是没有用的。这就提醒我们，已经被边权小的边更新过答案的区域，是不会再被更大的边更新的，在考虑每次更新是独立计算答案，最后需要的只是所有不在最小生成树上的边更新后叠加的值，对于更新的顺序完全不关心 那么我们就可以自定义更新顺序了，选择按照边权排序来更新就行 这样之前更新的区域就不用重复更新了，可以用类似并查集或者链表的方法跳着跳着更新还没有更新的区域
这样由于每个点只会被更新一次，复杂度就是均摊O（m）的了 不仅非常优秀而且意外好写
完整代码：
#include<stdio.h> #include<algorithm> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; struct edge { int v,u,last,w,id; }ed[400010],e[400010]; int n,m,tot=0,num=0,head[200010],anc[200010][20],st[200010][20]; int dep[200010],ans[200010],to[200010],fa[200010],used[200010]; bool cmp(const edge &a,const edge &b) { return a.w<b.w; } int getfather(int x) { if(x==fa[x]) return x; return fa[x]=getfather(fa[x]); } void add(int u,int v,int w,int id) { num++; ed[num].v=v; ed[num].id=id; ed[num].w=w; ed[num].last=head[u]; head[u]=num; } void dfs(int u,int f) { anc[u][0]=f; for(int i=1;i<=18;i++) { anc[u][i]=anc[anc[u][i-1]][i-1]; st[u][i]=max(st[u][i-1],st[anc[u][i-1]][i-1]); } for(int i=head[u];i;i=ed[i].last) { int v=ed[i].v; if(v==f) continue ; to[v]=ed[i].id; st[v][0]=ed[i].w; dep[v]=dep[u]+1; dfs(v,u); } } int lca(int u,int v,int &d) { d=0; if(dep[u]<dep[v]) swap(u,v); for(int i=18;i>=0;i--) if(dep[anc[u][i]]>=dep[v]) { d=max(d,st[u][i]); u=anc[u][i]; } if(u==v) return u; for(int i=18;i>=0;i--) if(anc[u][i]!=anc[v][i]) { d=max(d,st[u][i]),d=max(d,st[v][i]); u=anc[u][i],v=anc[v][i]; } d=max(d,st[u][0]),d=max(d,st[v][0]); return anc[u][0]; } void Kruscal() { sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,w=e[i].w; int x=getfather(u),y=getfather(v); if(x!=y) { fa[x]=y,used[i]=1; add(u,v,w,e[i].id); add(v,u,w,e[i].id); tot++; } if(tot==n-1) return ; } } void modify(int u,int v,int d) { u=getfather(u); while(dep[u]>dep[v]) { ans[to[u]]=min(ans[to[u]],d); int y=getfather(anc[u][0]); fa[u]=y; u=getfather(u); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].id=i; Kruscal(); dfs(1,1); memset(ans,INF,sizeof(ans)); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { if(used[i]) continue ; int u=e[i].u,v=e[i].v,f=lca(u,v,ans[e[i].id]); ans[e[i].id]--; modify(u,f,e[i].w-1); modify(v,f,e[i].w-1); } for(int i=1;i<=m;i++) if(ans[i]==INF) printf("-1\n"); else printf("%d\n",ans[i]); return 0; } /* EL PSY CONGROO */嗯，就是这样
