玄关超时一点点求卡常

#include<bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline ll read(){R ll x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=1e6+10;
int n,k;
struct edge
{
	int u,v;
    ll w;
}e[N];
vector<int>g[N],b[N];
vector<ll>w[N];
inline void add(int u,int v,ll wo)
{
	g[u].push_back(v);
	w[u].push_back(wo);
	return;
}
int fl[N],fa[N];
ll val1[N];
ll dep[N];
int flag,to[N],ww[N];
ll ans[N];
bool vis[N];
void dfs(int u,int Fa)
{
//	cout << u << " " << Fa << '\n';
	vis[u]=1;
	for(R int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==Fa) continue;
		if(!vis[v]){
			vis[v]=1;
			fa[v]=u;
			dfs(v,u);
		}
		else if(!flag){
			flag=1;
			while(u!=v){
		//		cout << u << "#" << v <<'\n';
				fl[u]=1;
				u=fa[u];
			}
			fl[v]=1;
		//	return;
		}
	}
}
ll val[N];
ll dis[N];
void dfs1(int u,int Fa,int rt)
{
	fa[u]=Fa;
	for(R int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(fl[v] || v==Fa) continue;
		b[rt].push_back(v);
		dis[v]=dis[u]+w[u][i];
		dep[v]=dep[u]+1;
		if(dep[v]>=k) val[rt]+=dis[v];
		dfs1(v,u,rt);
	}
	return;
}
ll sumup[N],siz[N],cf1[N],cf2[N];
inline int Get(int x,int dep)
{
	int rsum=dep;
	while(rsum--){
		if(fl[x] || x==0){
			return -1;
		}
		x=fa[x];
	}
	return x;
}
void dfs2(int u,int fa)
{
	siz[u]=1;
	for(R int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa || fl[v]) continue;
		dfs2(v,u);
		siz[u]+=siz[v];
		sumup[u]+=sumup[v]+siz[v]*w[u][i];
	}
	int anc2=Get(u,k-1);
	if(anc2==-1) return;
	int anc=Get(anc2,1);
	if(anc==-1) return;
	int rsum=siz[u]*(dis[u]-dis[anc])+sumup[u];//u子树内的所有点到anc的距离和
	cf1[anc]+=rsum,cf1[anc2]-=rsum;//差分
	cf2[anc]+=rsum*dis[anc],cf2[anc2]-=rsum*dis[anc];
}
void dfsdown(int u,int fa)
{
	for(R int i = 0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa || fl[v]) continue;
		cf1[v]+=cf1[u],cf2[v]+=cf2[u];
		dfsdown(v,u);
	}
	ans[u]+=dis[u]*cf1[u]-cf2[u];
//	if(cf1[u]) assert(0);
//	if(cf2[u]) assert(0);
//	if(ans[u]) assert(0);
}
signed main()
{
	n=read(),k=read();
	F(i,1,n){
		e[i].u=read(),e[i].v=read(),e[i].w=read();
		add(e[i].u,e[i].v,e[i].w);
		add(e[i].v,e[i].u,e[i].w);
	}
	dfs(1,0);
//	for(int i = 1;i<=n;i++){
//		if(fl[i]) cout << i << " ";
//	}
	//cout << '\n';
	memset(dep,0,sizeof dep);
	ll sumv=0;
	F(i,1,n){
		if(fl[i]){
			b[i].push_back(i);
			dfs1(i,0,i);
			sumv+=val[i];
			dfs2(i,0);
			dfsdown(i,0);
	//		cout << i << " " << val[i] << '\n';
		}
	}
	int st=0;
	ll sumw=0;
	F(i,1,n){
		if(fl[e[i].u] && fl[e[i].v]){
			to[e[i].u]=e[i].v;
			ww[e[i].u]=e[i].w;
			sumw+=e[i].w;
		}
	}
	F(i,1,n){
		if(fl[i]){
			st=i;
			break;
		}
	}
	int now=st;
	ll noww=0,nowv=0,fll=0;
	while(1){
		if(now==st){
			if(!fll) fll=1;
			else break;
		}
		noww+=ww[now];
		if(to[now]!=st) nowv+=noww*val[to[now]];
	//	cout<< now << " " << to[now] << " " << noww << " " << nowv << '\n';
		now=to[now];
	}
	now=st;
	fll=0;
	while(1){
		if(now==st){
			if(!fll) fll=1;
			else break;
		}
		for(int v:b[now]){
	//		cout << v << '\n';
			ans[v]+=dis[v]*(sumv-val[now]);
			ans[v]+=nowv;
		}
		nowv=nowv-ww[now]*(sumv-val[now]);
		nowv=nowv+val[now]*(sumw-ww[now]);
		now=to[now];
	}
	F(i,1,n) printf("%lld\n",ans[i]);
	return 0;
}
/*
8 1
1 4 3 
2 1 2 
3 1 6 
4 3 4 
5 2 4 
6 4 1 
7 5 2
8 5 2
*/