自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:17:08，当前版本为作者最后更新于2025-06-05 14:06:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

伟大的安徽字典序队长 FS_NEO 指出：

考虑固定起点和终点怎么计算答案。也就是做线性序列。

设 $pre_i$ 为从起点走 $i$ 步获得的代价（不采取最优策略）。

那么最终的得分是：$pre_t - \min_i pre_i$；清零次数为 $pre$ 的严格前缀最小值数量减一。

看到树上路径统计问题，想到点分治。

设分治中心是 $root$，我们会把路径拆成 $u \to root \to v$。

所以 $u \to v$ 的 $pre$ 折线实际上是 $u \to root$ 和 $root \to v$ 两条 $pre$ 折线拼起来。如图所示：

以 $u$ 开始的所有路径的 $pre_t$ 之和是好算的。考虑怎么算 $\min_i pre_i$ 之和。

对于蓝色的路径（从 $u$ 出发），我们只需要知道 $mn_1$ 和 $sum_1$；对于红色路径我们只需要知道 $mn_2$。拼在一起的最小值是 $\min\{mn_1,sum_1+mn_2\}$。随便维护一下 $mn_2$ 就行（比如用线段树）。

那么前缀最小值个数呢？首先考虑蓝色区域的前缀最小值个数，它们是不受影响的。容易使用树上倍增求出每个位置之后的第一个比他低的谷，如图所示：

对于红色部分，如果一个位置是拼接之后的前缀最小值，那么一定是原序列的前缀最小值，并且满足 $mn_1 > sum+mn_2$。如果这个不等式成立，那么这个红色位置一定是前缀最小值，不管它的后面是什么。所以这个节点会对 $sze_v$ 个点产生贡献。也容易使用线段树维护。

说起来容易，代码非常冗杂，而且有点卡常。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e5+10;const ll INF=1e12;
int n,dep[MAXN],FA[MAXN],fa[MAXN][20];
vector<pair<int,int>> G[MAXN];

ll pre[MAXN],mn[MAXN],mx[MAXN],ans1[MAXN],ans2[MAXN];
int sze[MAXN],cut[MAXN],mxs[MAXN];
inline void dfs1(const int u,const int f) {
	sze[u]=1,mxs[u]=0;
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f||cut[v]) continue ;
		dfs1(v,u),mxs[u]=max(mxs[u],sze[v]),sze[u]+=sze[v];
	}
	return ;
}
vector<int> bel[MAXN];
inline int find_core(const int u,const int f,const int al) {
	if(max(mxs[u],al-sze[u])<=al/2) return u;
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f||cut[v]) continue ;
		int tans=find_core(v,u,al);
		if(tans!=-1) return tans;
	}
	return -1;
}
inline void dfs2(const int u,const int f,const int LIM) {
	mx[u]=mn[u]=pre[u],sze[u]=1,FA[u]=f;
	if(f) mx[u]=max(mx[u],mx[f]),mn[u]=min(mn[u],mn[f]);
	if(f) {
		if(pre[f]>pre[u]) fa[u][0]=f,dep[u]=dep[f]+1;
		else if(pre[u]>=mx[f]) fa[u][0]=u,dep[u]=0;
		else {
			int pos=f;
			roff(i,LIM,0) if(pre[fa[pos][i]]<=pre[u]) pos=fa[pos][i];
			pos=fa[pos][0],fa[u][0]=pos,dep[u]=dep[pos]+1;
		}
		ffor(i,1,LIM) fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	else ffor(i,0,LIM) fa[u][i]=0;
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f||cut[v]) continue ;
		pre[v]=pre[u]+w,dfs2(v,u,LIM),sze[u]+=sze[v];
	}
	return ;
}
struct INFO {ll sze,val;int cnt;};
namespace SGT {
	const int MAXM=1.5e7+10;
	int tot=0;
	struct Node {int ls,rs;ll sze,val;int cnt;}t[MAXM];
	inline INFO operator +(const INFO A,const INFO B) {return {A.sze+B.sze,A.val+B.val,A.cnt+B.cnt};}
	inline void init(void) {return tot=0,void();}
	inline int get_node(void) {return ++tot,t[tot]={0,0,0,0,0},tot;}
	inline void update(int &u,const ll l,const ll r,const ll x,const int dsze,const ll dval,const int dcnt) {
		if(!u) u=get_node();
		t[u].sze+=dsze,t[u].val+=dval,t[u].cnt+=dcnt;
		if(l!=r) {
			ll mid=l+(r-l)/2;
			if(x<=mid) update(t[u].ls,l,mid,x,dsze,dval,dcnt);	
			else update(t[u].rs,mid+1,r,x,dsze,dval,dcnt);
		}
		return ;
	}
	inline INFO query(const int u,const ll l,const ll r,const ll x,const ll y) {
		if(!u) return {0,0,0};
		if(x<=l&&r<=y) return {t[u].sze,t[u].val,t[u].cnt};
		INFO ans={0,0,0};
		ll mid=l+(r-l)/2;
		if(x<=mid) ans=ans+query(t[u].ls,l,mid,x,y);
		if(y>mid) ans=ans+query(t[u].rs,mid+1,r,x,y);
		return ans;
	}
};
inline void mark(const int u,const int f,const int anc) {
	bel[anc].push_back(u);
	for(auto pr:G[u]) {
		int v=pr.first,w=pr.second;
		if(v==f||cut[v]) continue ;
		mark(v,u,anc);	
	}
	return ;
}
inline void solve(int u) {
	dfs1(u,0);
	if(sze[u]==1) return cut[u]=1,void();
	int lim=__lg(sze[u]/2);
	u=find_core(u,0,sze[u]);
	dep[u]=pre[u]=mn[u]=mx[u]=0,dfs2(u,0,lim);
	bel[u].clear(),bel[u].push_back(u);
	vector<int> T;
	for(auto pr:G[u]) {
		int v=pr.first;
		if(cut[v]) continue ;
		T.push_back(v);	
	}
	bel[u].clear(),bel[u].push_back(u);
	for(auto v:T) bel[v].clear(),mark(v,u,v);
	vector<int> S=T; S.push_back(u);
	
	SGT::init();
	int rt=0;ll ts=0;
	for(auto id:S) {
		for(auto v:bel[id]) {
			ll sum1=pre[v],mn1=pre[v]-mx[v];
			INFO L;
			if(rt) L={SGT::t[rt].sze,SGT::t[rt].val,SGT::t[rt].cnt};
			else L={0,0,0};
			INFO R=SGT::query(rt,-INF,INF,mn1-sum1,INF);
			L.sze=L.sze-R.sze,L.val=L.val-R.val,L.cnt=L.cnt-R.cnt;
			ans1[v]+=(sum1*(L.cnt+R.cnt)+ts)-(sum1*L.cnt+L.val+R.cnt*mn1);
			ans2[v]+=1ll*dep[v]*(L.cnt+R.cnt)+L.sze;
		}
		for(auto v:bel[id]) {
			ll dsze=0,dval=mn[v],dcnt=1;
			if(v!=u&&pre[v]<mn[FA[v]]) dsze=sze[v];
			SGT::update(rt,-INF,INF,mn[v],dsze,dval,dcnt),ts+=pre[v];
		}
	}
	SGT::init(),rt=0,ts=0,reverse(S.begin(),S.end());
	for(auto id:S) {
		for(auto v:bel[id]) {
			ll sum1=pre[v],mn1=pre[v]-mx[v];
			INFO L;
			if(rt) L={SGT::t[rt].sze,SGT::t[rt].val,SGT::t[rt].cnt};
			else L={0,0,0};
			INFO R=SGT::query(rt,-INF,INF,mn1-sum1,INF);
			L.sze=L.sze-R.sze,L.val=L.val-R.val,L.cnt=L.cnt-R.cnt;
			ans1[v]+=(sum1*(L.cnt+R.cnt)+ts)-(sum1*L.cnt+L.val+R.cnt*mn1);
			ans2[v]+=1ll*dep[v]*(L.cnt+R.cnt)+L.sze;
		}
		for(auto v:bel[id]) {
			ll dsze=0,dval=mn[v],dcnt=1;
			if(v!=u&&pre[v]<mn[FA[v]]) dsze=sze[v];
			SGT::update(rt,-INF,INF,mn[v],dsze,dval,dcnt),ts+=pre[v];
		}
	}
	
	cut[u]=1;
	for(auto v:T) solve(v);
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n-1) {
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w}),G[v].push_back({u,w});
	}
	solve(1);
	cout<<1<<'\n';
	ffor(i,1,n) cout<<ans1[i]<<' '; cout<<'\n';
	ffor(i,1,n) cout<<ans2[i]<<' '; cout<<'\n';
	return 0;
}