Znzryb's Blog

START203——Subsequences of Subsequences（如何求偶数长度子序列的异或和的最大值）

Posted on 2025-09-11 Edited on 2026-04-06

思路讲解

遇到这种题目不要慌，首先不难发现是线性基。

接着我们不要一下子想特别复杂的情况，我们就想一想 K=2 的时候是怎么样的？

// 因为两段不同的段，相互遮盖的长度是一样的。
// 奇数加奇数是偶数，偶数加偶数还是偶数
// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。

    这里用到了一个小技巧

就是这个我们知道，如果说我们只要求偶数长度子序列的
        异或最大值怎么办呢？
        这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
        就说明是奇数长度子序列得到的和
        否则就是偶数长度子序列得到的和。

AC代码

https://www.codechef.com/viewsolution/1190285113

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> lT;
	while (lT--)
		__();
	return 0;
}
/*
直接模拟肯定不行吗？

用 python 不难得出该结论
*/
vll base;
void add(ll x) {
	FOR(i, 0, SZ(base) -1) {
		x = min(x, x ^ base[i]);
	}
	if (x != 0) base.PB(x);
}
ll count() {
	ll res = 1ll << SZ(base);
	return res;
}
inline void __() {
	cin >> N >> K;
	vll A(N + 5);
	base.clear();
	// 这边需要特判一下。
	if (N == K) {
		ll res = 0;
		FOR(i, 1, N) {
			cin >> A[i];
			res ^= A[i];
		}
		if (res == 0) {
			cout << 1 << "\n";
		} else {
			cout << 2 << "\n";
		}
		return;
	}
	// 因为两段不同的段，相互遮盖的长度是一样的。
	// 奇数加奇数是偶数，偶数加偶数还是偶数
	// 遮盖以后都是加减偶数，并不会影响段的长度的奇偶性。
	if (K & 1) {
		FOR(i, 1, N) {
			cin >> A[i];
			add(A[i]);
		}
		cout <<	count() << "\n";
	} else {
		/*
		这里用到了一个小技巧
		就是这个我们知道，如果说我们只要求偶数长度子序列的
		异或最大值怎么办呢？
		这个时候可以给加入线性基的数字加一个标记，如果最后这个值有标记
		就说明是奇数长度子序列得到的和
		否则就是偶数长度子序列得到的和。
		*/
		ll flag = 1ll << 31;
		FOR(i, 1, N) {
			cin >> A[i];
			add(A[i]^flag);
		}
		ll res = 1ll << (SZ(base) -1);
		// reduced row echelon form （RREF）
		// 我们利用阶梯型行列式REF的性质
		// 只会出现一个含有flag 的数字，因此剪掉就行了。
		cout << res << "\n";
	}
}
/*
AC
https://www.codechef.com/viewsolution/1190285113
1
4 1
1 2 4 8


1
3 3
0 0 0

1
1 1
0

*/

心路历程（WA，TLE，MLE……）

START203——MEX on Ranges

Posted on 2025-09-10 Edited on 2026-04-06

思路讲解

其他都想到了，就是这个

reverse(all(wp));

需要hack数据才能想到。

其实1 1 之间不会相互影响，但是0 0之间会，把最重要的放在最远，避免互相影响。

	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}

AC代码

https://www.codechef.com/viewsolution/1189976308

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*

*/
inline void __(){
	cin>>N;
	string s;
	cin>>s;
//	vll A(N+5);
	deque<ll> A;
	vll wp;
	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}
	FOR(i,0,SZ(wp)-1){
		A.PB(N);
	}
	for(auto a:A){
		cout<<a<<" ";
	}
	cout<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1189976308

1
4
11001

既然考虑到了 1 1 的情况，也要考虑0 0 的情况

//		if(i&1){
//			A.PB(t);
//		}else{
//			A.PF(t);
//		}


//	vb suf(N+5);
//	ROF(i,N,0){
//		if(s[i]=='1'){
//			suf[i]=true;
//			continue;
//		}
//		suf[i]=suf[i+1];
//	}
//	FOR(i,1,N){
//		if(s[i]=='1') continue;
//		if(suf[i]){
//			A.PB(i-1);
//		}else{
//			A.PB(N);
//		}
//	}


*/

心路历程（WA，TLE，MLE……）

Codeforces Round 1048 (Div. 2)——E2. Maple and Tree Beauty (Hard Version)（bitset的使用，变长bitset）

Posted on 2025-09-10 Edited on 2026-04-06

思路讲解

Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和）

不难发现，用背包会TLE。

说实话，这个就真没招了，看题解吧。

其实用bitset 优化一下就能过去。

最后发现，我这样分一个if else 的反而更快

还有一种曲线救国方法。使用模板参数。

template <int maxn>
inline void __() {
//	cin >> N >> K;
	if (maxn <= N) {
		__< min(maxn * 2, (int)MAXN) >();
		return;
	}

AC代码

https://codeforces.com/contest/2139/submission/337943651

$O(N^2/w)$ 的时间复杂度，能够过去。

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <bitset>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long; using ull = unsigned long long;
using DB = double; using LD = long double;
// using i128 = __int128;
using pdd = pair<DB, DB>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<DB>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)2e5+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> lT;
	while (lT--)
		__();
	return 0;
}
/*
双背包问题解法
https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a


*/
inline void __() {
	cin >> N >> K;
	vll P(N + 5);
	vector<vll> g(N + 5);
	FOR(i, 2, N) {
		cin >> P[i];
		g[i].PB(P[i]);
		g[P[i]].PB(i);
	}
	vll cnt(N + 5);
	ll desti = INF;
	auto dfs = [&](auto &&self, int u, int fa, int dep)->void {
		cnt[dep]++;
		bool isleaf = true;
		for (auto &v : g[u]) {
			if (v == fa) continue;
			self(self, v, u, dep + 1);
			isleaf = false;
		}
		if (isleaf) {
			desti = min<ll>(desti, dep);
		}
	};
	dfs(dfs, 1, 1, 1);
	vll ls = {0};
	FOR(i, 1, desti) {
		ls.PB(cnt[i]);
	}
	// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
	// 我们直接看前 K 个物品是否可以凑出一个和
	// vector<vii> dp(SZ(ls)+5,vii(N+5));
	if (K <= N - K) {
		K = N - K;
	}
	ll ans = 0;
	if (N <= 200) {
		bitset<210> dp;
		ll sum = 0;
		// 滚动数组优化，第i层哪些值是可以达到的
		dp[0] = true;
		bitset<210> mask;
		FOR(i, 0, K) {
			mask[i] = true;
		}
		ll up = K - N;
		FOR(i, 1, desti) {
			ll w = ls[i];
			sum += w;
			dp |= (dp << w);
			ll cur = sum - N + K - 1;
			FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
				debug(j);
#endif
				mask[j] = 0;
			}
			up = cur;
			// 这一大段代码
			// sum-N+K<=val<=K
			if ((mask & dp).any()) {
				ans = i;
			} else {
				break;
			}
		}
	} else {
		bitset<MAXN> dp;
		ll sum = 0;
		// 滚动数组优化，第i层哪些值是可以达到的
		dp[0] = true;
		bitset<MAXN> mask;
		FOR(i, 0, K) {
			mask[i] = true;
		}
		ll up = K - N;
		FOR(i, 1, desti) {
			ll w = ls[i];
			sum += w;
			dp |= (dp << w);
			ll cur = sum - N + K - 1;
			FOR(j, max(0ll, up), min(K, cur)) {
#ifdef LOCAL
				debug(j);
#endif
				mask[j] = 0;
			}
			up = cur;
			// 这一大段代码
			// sum-N+K<=val<=K
			if ((mask & dp).any()) {
				ans = i;
			} else {
				break;
			}
		}
	}
	cout << ans << "\n";
}
/*
AC
https://codeforces.com/contest/2139/submission/337943651
1
5 2
1 1 1 1

*/

心路历程（WA，TLE，MLE……）

Codeforces Round 1048 (Div. 2)——E1. Maple and Tree Beauty (Easy Version)（背包问题）（子集枚举→能否凑出某个的和）

Posted on 2025-09-10 Edited on 2026-04-06

思路讲解

https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a

// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
// 我们直接看前 K 个物品是否可以凑出一个和
// vector<vii> dp(SZ(ls)+5,vii(N+5));
vii dp(N+5);
ll sum=0;
ll ans=0;
// 滚动数组优化，第i层哪些值是可以达到的
dp[0]=true;
FOR(i,1,desti){
	ll w=ls[i];
	sum+=w;
	// 滚动数组反向遍历
	ROF(j,N-w,0){
		dp[w+j]|=dp[j];
	}
	FOR(a,0,N){
		if(dp[a]){
			ll b=sum-a;
			if((a<=K && b<=N-K) || (b<=K && a<=N-K) ){
				ans=i;
				break;
			}
		}
	}
	if(ans!=i){
		break;
	}
}

AC代码

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#include <vector>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e3+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*
双背包问题解法
https://chatgpt.com/share/68c0ff99-20d0-8013-b16a-26d60768748a


*/
inline void __(){
	cin>>N>>K;
	vll P(N+5);
	vector<vll> g(N+5);
	FOR(i,2,N){
		cin>>P[i];
		g[i].PB(P[i]);
		g[P[i]].PB(i);
	}
	vll cnt(N+5);
	ll desti=INF;
	auto dfs=[&](auto &&self,int u,int fa,int dep)->void {
		cnt[dep]++;
		bool isleaf=true;
		for(auto &v:g[u]){
			if(v==fa) continue;
			self(self,v,u,dep+1);
			isleaf=false;
		}
		if(isleaf){
			desti=min<ll>(desti,dep);
		}
	};
	dfs(dfs,1,1,1);
	vll ls={0};
	FOR(i,1,desti){
		ls.PB(cnt[i]);
	}
	// 我们会发现，能否通过前K关（构造出K前缀），和这个顺序是没有关系的
	// 我们直接看前 K 个物品是否可以凑出一个和
	// vector<vii> dp(SZ(ls)+5,vii(N+5));
	vii dp(N+5);
	ll sum=0;
	ll ans=0;
	// 滚动数组优化，第i层哪些值是可以达到的
	dp[0]=true;
#ifdef LOCAL
	_print(ls);
#endif
	FOR(i,1,desti){
		ll w=ls[i];
		sum+=w;
		// 滚动数组反向遍历
		ROF(j,N-w,0){
			dp[w+j]|=dp[j];
		}
		FOR(a,0,N){
			if(dp[a]){
				ll b=sum-a;
#ifdef LOCAL
				debug(a)
				debug(b);
#endif
				if((a<=K && b<=N-K) || (b<=K && a<=N-K) ){
					ans=i;
					break;
				}
			}
		}
		if(ans!=i){
			break;
		}
	}
	cout<<ans<<"\n";
}
/*
AC
https://codeforces.com/contest/2139/submission/337899174
*/

心路历程（WA，TLE，MLE……）

Teleporter（传送门，使用至少0，1，。。。N次传送门的最短路）

Posted on 2025-09-09 Edited on 2026-04-06

思路讲解

注意，不能直接跑分层图，会TLE。

那怎么办呢？可以用传送门，先确定一些种子节点，再跑多源最短路。

一个比较重要的剪枝其实在这里。

FOR(j, 1, N) {
	Dis[i][j] = Dis[i - 1][j];
}
priority_queue < DIS > pq;
FOR(u, 1, N) {
	for (auto &v : jie[u]) {
		Dis[i][u] = min(Dis[i - 1][v], Dis[i][u]);
	}
}
FOR(u, 1, N) {
	// 超了，或者和原来一样，就不要了
	if (Dis[i][u] != Dis[i - 1][u]) {
		pq.push({Dis[i][u], u});
	}
}

AC代码

914ms，在dij中算跑的很快的。

https://qoj.ac/submission/1310755

源代码

// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef _DEBUG
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long; using ull = unsigned long long;
using ld = double; using LD = long double;
using i128 = __int128;
using pdd = pair<ld, ld>; using plb = pair<ll, bool>;
using pll = pair<ll, ll>; using vll = vector<ll>; using vb = vector<bool>;
using tll = tuple<ll, ll, ll>; using vii = vector<int>;
using vpll = vector<pll>; using vtll = vector<tll>;
using vdb = vector<ld>; using vc = vector<char>;
using arr3 = array<ll, 3> ; using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)5e3+10, INF = (ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9+7; // 998244353;
static constexpr double eps = 1e-8; const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;

inline void __();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

//	cin>>lT;
//	while(lT--)
	__();
	return 0;
}
/*

*/
vector<arr2> g[MAXN];
vector<ll> jie[MAXN];
bool vis[MAXN][MAXN];
ll Dis[MAXN][MAXN];
ll ans[MAXN];
void dfs(int u, int fa) {
	for (auto &[v, w] : g[u]) {
		if (v == fa) continue;
		Dis[0][v] = Dis[0][u] + w;
		ans[0] += Dis[0][v];
		dfs(v, u);
	}
}
struct DIS{
	ll dis, u;
	bool operator<(const DIS & o) const{
		return dis > o.dis;
	}
};
arr2 edge[2 * MAXN];
inline void __() {
	cin >> N >> M;
	FOR(i, 1, N - 1) {
		ll u, v, w;
		cin >> u >> v >> w;
		g[u].PB({v, w});
		g[v].PB({u, w});
	}
	FOR(i, 0, N + 5) {
		FOR(j, 0, N + 5) {
			Dis[i][j] = INF;
		}
	}
	vector < ll > li;
	FOR(i, 1, M) {
//		cin >> edge[i][0] >> edge[i][1];
		ll u, v;
		cin >> u >> v;
		jie[u].PB(v);
		jie[v].PB(u);
	}
	Dis[0][1] = 0;
	dfs(1, 1);
	FOR(i, 1, N) {
		FOR(j, 1, N) {
			Dis[i][j] = Dis[i - 1][j];
		}
		priority_queue < DIS > pq;
		FOR(u, 1, N) {
			for (auto &v : jie[u]) {
				Dis[i][u] = min(Dis[i - 1][v], Dis[i][u]);
			}
		}
		FOR(u, 1, N) {
			if (Dis[i][u] != Dis[i - 1][u]) {
				pq.push({Dis[i][u], u});
			}
		}
//#ifdef LOCAL
//		debug(pq.empty());
//#endif
		while (!pq.empty()) {
			auto[dis, u] = pq.top();
			pq.pop();
			if (vis[i][u]) continue;
			vis[i][u] = true;
			Dis[i][u] = dis;
			for (auto &[v, w] : g[u]) {
				if (vis[i][v]) continue;
				if (dis + w >= Dis[i][v]) continue;
				pq.push({dis + w, v});
				Dis[i][v] = dis + w;
			}
		}
		FOR(j, 1, N) {
			ans[i] += Dis[i][j];
		}
		if (ans[i] == ans[i - 1]) {
			FOR(j, i + 1, N) {
				ans[j] = ans[i];
			}
			break;
		}
	}
	FOR(lim, 0, N) {
		cout << ans[lim] << "\n";
	}

}
/*
TLE
https://vjudge.net/solution/63520490
赛时可以 A 过去

AC  914 ms
https://qoj.ac/submission/1310755
*/