什么神仙题啊，我怎么只会(dsu)啊
我们考虑一个非常暴力的操作，我们利用(dsu on tree)把一棵子树内部的非树边都搞出来，用一个堆来存储
我们从堆顶开始暴力所有的边，如果这条边指向的另外一个点不在当前子树里，我们就把这条边计入答案
这样复杂度显然不是很对，因为我们每次可能要把子树里的边全都访问上一次
考虑让这个暴力的复杂度科学一点
我们发现，如果有一条边在当前这个节点不合法，也就是指向了一个子树内部的边，非常显然，这个点在更往上的点里也会不合法，所以我们直接在这里把这条边给删掉，这样我们就能保证每一条边最多只会被暴力一次了
代码
#include<set>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define re register
#define LL long long
#define mp std::make_pair
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int inf=999999999;
typedef std::pair<int,int> pii;
const int maxn=1e5+5;
struct E{int v,nxt,w;}e[maxn<<1];
int n,m,num,ans[maxn],Son,__;
int pre[maxn],head[maxn],sum[maxn],son[maxn],dfn[maxn];
std::set<pii> s[maxn];
std::set<pii>::iterator it;
typedef std::pair<int,pii> Pi;
std::priority_queue<Pi,std::vector<Pi>,std::greater<Pi> > q;
inline void Con(int x,int y,int z) {
e[++num].v=y;e[num].nxt=head[x];
head[x]=num;e[num].w=z;
}
void dfs1(int x) {
sum[x]=1;dfn[x]=++__;
for(re int i=head[x];i;i=e[i].nxt) {
pre[e[i].v]=pre[x]+e[i].w;
dfs1(e[i].v);sum[x]+=sum[e[i].v];
if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;
}
}
namespace Dij {
std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
struct E{int v,nxt,w;}e[400005];
int d[maxn],vis[maxn],fa[maxn];
int num,head[maxn];
inline void add(int x,int y,int z) {
e[++num].v=y;e[num].nxt=head[x];
head[x]=num;e[num].w=z;
}
inline void work() {
for(re int x,y,z,i=1;i<=m;i++) {
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
for(re int i=2;i<=n;i++) d[i]=inf;
q.push(mp(0,1));
while(!q.empty()) {
int k=q.top().second;q.pop();
if(vis[k]) continue;vis[k]=1;
for(re int i=head[k];i;i=e[i].nxt)
if(d[e[i].v]>d[k]+e[i].w) {
d[e[i].v]=d[k]+e[i].w;fa[e[i].v]=k;pre[e[i].v]=e[i].w;
q.push(mp(d[e[i].v],e[i].v));
}
}
for(re int i=2;i<=n;i++) Con(fa[i],i,pre[i]);
dfs1(1);
for(re int i=1;i<=n;i++)
for(re int j=head[i];j;j=e[j].nxt) {
if(fa[i]==e[j].v||fa[e[j].v]==i) continue;
s[i].insert(mp(e[j].v,pre[e[j].v]+pre[i]+e[j].w));
}
}
}
void calc(int x) {
for(it=s[x].begin();it!=s[x].end();++it) {
pii now=(*it);
q.push(mp(now.se,mp(x,now.fi)));
}
for(re int i=head[x];i;i=e[i].nxt)
if(Son!=e[i].v) calc(e[i].v);
}
inline void del(int a,int b,int c) {
it=s[a].find(mp(b,c));s[a].erase(it);
}
void dfs(int x,int k) {
for(re int i=head[x];i;i=e[i].nxt)
if(son[x]!=e[i].v) dfs(e[i].v,0);
if(son[x]) dfs(son[x],1);
if(x==1) return;
Son=son[x],calc(x);Son=0;
while(!q.empty()) {
int now=q.top().fi,k=q.top().se.se,t=q.top().se.fi;
if(dfn[k]>=dfn[x]&&dfn[k]<=sum[x]+dfn[x]-1) {del(t,k,now);q.pop();continue;}
ans[x]=now-pre[x];break;
}
if(!k) while(!q.empty()) q.pop();
}
int main() {
n=read(),m=read();Dij::work();
dfs(1,1);
for(re int i=2;i<=n;i++)
if(!ans[i]) puts("-1");else printf("%d
",ans[i]);
return 0;
}