https://www.luogu.org/problemnew/show/P4374
一看这道题就是一个妙题，然后题解什么树链剖分...珂朵莉树...
还不如并查集来的实在！我们知道并查集本来就是路径压缩的。
比如这题可以树上的路径压缩！！ 直接跳到father，就省去大量上跳的过程（因为我们已经计算过了，不存在最优了）。
下面给出题面：
给出n个节点的树，现在有m条边可供替换，对于树上每一条边删除，
为了保证整颗树强连通，需要从给出的边中选出一条添加上，
求对于删除的每一条树边，最小添加上的给出的边的长度。
对于100%的数据 $n leq 5 imes 10^4 $
做法的话就是首先建这棵树然后把每一条边记录它的编号i然后LCA预处理都会的吧
按照边权排序然后枚举这条边可以完成哪些边删除后的替代作用，显然的一个贪心，前面枚举的边权小如果被小边权选过了
那么后面的边即使可以选上也一定比前面的边权大，所以只要可行，我们就使用并查集把这条边直接折叠掉，下次不做遍历。
对于每一条边的答案存在它的末端，可以比较方便处理。暴力找不断按照father跳到lca及以上就行。
code ：
# include <cstdio> # include <algorithm> using namespace std; const int N=5e4+10; struct rec{ int u,v,w; }e[N]; struct Edg{ int pre,to,id; }a[N<<1]; int n,m,tot; int dep[N],g[N][25],f[N],head[N],arc[N],ans[N]; inline int read() { int X=0,w=0; char c=0; while(c<'0'||c>'9') {w|=c=='-';c=getchar();} while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } void swap(int &x,int &y){int t=x;x=y;y=t;} void write(int x) { if (x==-1) { putchar('-'); putchar('1'); return;} if (x>9) write(x/10); putchar(x%10+'0'); } void adde(int id,int u,int v) { a[++tot].pre=head[u]; a[tot].to=v; a[tot].id=id; head[u]=tot; } int father(int x) { if (f[x]==x) return x; return f[x]=father(f[x]); } bool cmp(rec aa,rec bb){return aa.w<bb.w;} void dfs(int u,int fath) { g[u][0]=fath; dep[u]=dep[fath]+1; for (int i=head[u];i;i=a[i].pre) { int v=a[i].to; if (v==fath) continue; arc[a[i].id]=v; dfs(v,u); } } void init() { for (int j=1;j<=21;j++) for (int i=1;i<=n;i++) g[i][j]=g[g[i][j-1]][j-1]; } int lca(int u,int v) { if (dep[u]<dep[v]) swap(u,v); for (int i=21;i>=0;i--) if (dep[g[u][i]]>=dep[v]) u=g[u][i]; if (u==v) return u; for (int i=21;i>=0;i--) if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i]; return g[u][0]; } int main() { n=read();m=read(); int u,v; for (int i=1;i<n;i++) { u=read();v=read(); adde(i,u,v); adde(i,v,u); } dfs(1,0); init(); for (int i=1;i<=m;i++) e[i]=(rec){read(),read(),read()}; sort(e+1,e+1+m,cmp); for (int i=1;i<=n;i++) f[i]=i,ans[i]=-1; for (int i=1;i<=m;i++) { int w=e[i].w,u=e[i].u,v=e[i].v,Lca=lca(u,v); for (u=father(u);dep[u]>dep[Lca];u=father(g[u][0])) ans[u]=w,f[u]=g[u][0]; for (v=father(v);dep[v]>dep[Lca];v=father(g[v][0])) ans[v]=w,f[v]=g[v][0]; } for (int i=1;i<n;i++) write(ans[arc[i]]),putchar(' '); return 0; }