2025牛客暑期多校训练营2-做题&补题记录

从头到尾难绷的一场，感觉五小时一直在卡题。小羊场细节有点太多了。

不过现在发现心态越来越好了，越打越乐，已经超然物外辣！（）

---

I Identical Somehow

两三眼出了结论，但是不敢交。又验证了一个例子才交，痛失二血。（

什么证明？Guess就完了

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    i64 x, y;
    cin >> x >> y;
    if (x != 1 && y != 1) {
        cout << 1 << "\n";
        return;
    }
    cout << -1 << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

B Bitwise Perfect

分析题目条件发现实际上是判断所有ai^aj>=max(ai,aj)。降序排序，维护一个前缀按位或的掩码，如果当前数最高位在掩码中出现，那么必然有一个数和当前数异或之后会小于当前数，那么非法。否则更新掩码。扫完数组输出答案。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    i64 mask = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    ranges::sort(a, greater<i64>());
    int ok = 1;
    for (int i = 0; i < n; ++i) {
        i64 hbt = 0;
        for (int j = 63; j >= 0; --j) {
            if (a[i] & (1LL << j)) {
                hbt = j;
                break;
            }
        }
        if ((mask & (1LL << hbt)) != 0) {
            ok = 0;
            break;
        }
        
        mask |= a[i];
    }
    cout << (ok ? "YES" : "NO") << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

F Field of Fire

一眼出思路，找所有的连续0的段，肯定是在最长的一段的一端点火更优，这一段只会烧毁t+1，其他段烧毁2t，计算答案即可。但是糖丸，多烧的那个1第一发减到最后res里了。我服了

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, t;
    cin >> n >> t;
    string s;
    cin >> s;
    vector<int> v;
    v.reserve(n);
    int st = s.find('1');
    int ed = s.find_last_of('1');
    //debug(st, ed);
    if (st == -1) {
        cout << 0 << "\n";
        return;
    }
    {
        int len = st + (n - 1 - ed);
        //debug(len);
        v.push_back(len);
    }
    for (int i = st + 1, len = 0; i <= ed; ++i) {
        if (s[i] == '0') {
            len++;
        } else {
            if (len) v.push_back(len);
            len = 0;
        }
    }
    ranges::sort(v, greater<int>());
    // for (int x : v) {
    //     cout << x << " ";
    // }
    // cout << endl;
    int res = max(0, v[0] - t - 1);
    for (int i = 1; i < v.size(); ++i) {
        res += max(0, v[i] - 2 * t);
    }
    cout << res << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

A Another Day of Sun

DP。思洋写的

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T,typename U>
ostream& operator<<(ostream& o,const tuple<T,U>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	o<<"[";
	for(int i=0;i<vec.size();++i){
		o<<vec[i];
		if(i!=vec.size()-1)o<<",";
	}
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 998244353;
constexpr double pi = acos(-1), eps = 1e-9;

void solve(){
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	vector<array<ll, 2>> dp(n + 1);
	ll t=1;
	for (int i = 1; i <= n; ++i) {
		dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
		dp[i][1]=((a[i-1]!=1)*(dp[i-1][0]+(t*(a[i-1]==-1?(mod+1)/2:1)))%mod+dp[i-1][1])%mod;
		if(a[i]==-1){
			t=t*2%mod;
		}
		else{
			dp[i][a[i]^1]=0;
		}
		// cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
	}
	cout << (dp[n][0] + dp[n][1]) % mod << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

L Love Wins All

出了思路没写完然后跑出门开会一个小时，思洋调完的。

按题意，必然是若干个环，那么只有0个奇环和2个奇环的情况合法。2个奇环就各自开一刀，0个奇环就选一个偶环开两刀。没被开刀的偶环只有2种方案，奇环开刀就size种方案，偶环开两刀有点复杂，分讨一下。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<int> fa(n + 1);
    iota(all(fa), 0);
    auto find = [&](int x) {
        while (x != fa[x]) {
            x=fa[x]=fa[fa[x]];
        }
        return x;
    };
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        fa[find(i)] = find(a[i]);
    }
    vector<i64> cnt(n + 1);
    for (int i = 1; i <= n; ++i) {
        cnt[find(i)]++;
    }
    // for (int i = 1; i <= n; ++i) {
    //     cout << fa[i] << " \n"[i == n];
    // }
    int odd = 0, even = 0;
    for (auto x : cnt) {
        if (!x || x == 2) continue;
        // debug(x);
        odd += (x % 2 == 1);
        even += (x % 2 == 0);
    }
    // debug(odd, even);
    if (odd != 0 && odd != 2) {
        cout << 0 << "\n";
        return;
    }
    i64 ans = 0;
    if (odd == 0) {
        i64 p = 1;
        for (int i = 1; i < even; ++i) p = p * 2 % MOD;
        for (auto x : cnt) {
            if(!x)continue;
            if(even > 0 && x == 2) ans += 2ll * p % MOD;
            else ans += 1LL * x * x / 4 % MOD * p % MOD;
            ans %= MOD;
        }
    } else {
        ans = 1;
        for (auto x : cnt) {
            if (!x || x == 2) continue;
            if (x & 1) {
                ans *= x;
            } else {
                ans *= 2;
            }
            ans %= MOD;
        } 
    }
    cout << ans << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

G Geometry Friend

开完会回来思洋在调这个。想了个hack样例然后过了。思洋还是泰牛。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T,typename U>
ostream& operator<<(ostream& o,const tuple<T,U>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	o<<"[";
	for(int i=0;i<vec.size();++i){
		o<<vec[i];
		if(i!=vec.size()-1)o<<",";
	}
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 1e9+7;// 998244353;
constexpr long double pi = acos(-1), eps = 1e-9;

struct point{
	ll x,y;
	point operator-(const point& p)const{
		return point(x-p.x,y-p.y);
	}
	ull m2(){
		return ull(x*x)+ull(y*y);
	}
	long double ang(){
		return atan2<long double>(y,x);
	}
	ll operator*(const point& p)const{
		return x*p.y-y*p.x;
	}
};

void solve(){
	int n;
	point p;
	cin>>n>>p.x>>p.y;
	vector<point> vec(n);
	ull m=0;
	for(auto& a:vec){
		cin>>a.x>>a.y;
		a=a-p;
		m=max(m,a.m2());
	}
	bool flag=false;
	for(int i=0,s=vec.size();i<s;++i){
		ll t=vec[(i+1)%s]*vec[i];
		if(t>0)flag=true;
	}
	vector<long double> ang;
	for(auto& a:vec){
		if(a.m2()==m)ang.emplace_back(a.ang());
	}
	// cout<<fixed<<setprecision(18)<<ang;
	long double ans=0.0L;
	for(int i=0,s=ang.size();i<s;++i){
		long double a=ang[(i+1)%s]-ang[i];
		if(a<=0.0)a+=2.0L*pi;
		// cout<<fixed<<setprecision(3)<<"% "<<a<<"\n";
		ans=max(ans,a);
	}
	if(flag)ans=2.0L*pi;
	cout<<fixed<<setprecision(18)<<ans<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

H Highway Upgrade

出了思路但是没有李超树板子。但是我有鱼鱼蒸。我黑化了。

要么凸包要么李超树，凸包插个眼完了看看怎么写。李超树比较无脑直接套板子。但是没学，洛谷上的模板也不好用。

学了一下，发现一点不难。这题就是最短路+李超树维护最小值。绷，只能说还好不是在赛场上发现出思路不会写。加训吧。您队封榜后没出过一题。我服了。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr i64 N = 3e5 + 10;
constexpr i64 M = 1e18;

#define lc(x) t[x].l
#define rc(x) t[x].r
struct node {
    int l, r;
    int k;
    i64 b = 1e18;
} t[N * 30];
int idx;

i64 calc(int k, i64 b, i64 x) {
    return k * x + b;
}

void modify(int& x, i64 l, i64 r, int k, i64 b) {
    if (!x) {
        x = ++idx;
        lc(x) = rc(x) = 0;
        t[x].k = k;
        t[x].b = b;
        return;
    }
    i64 mid = l + r >> 1;
    if (calc(k, b, mid) < calc(t[x].k, t[x].b, mid)) {
        swap(k, t[x].k);
        swap(b, t[x].b);
    }
    if (l == r) return;
    if (k < t[x].k) modify(rc(x), mid + 1, r, k, b);
    else modify(lc(x), l, mid, k, b);
}

i64 query(int x, i64 l, i64 r, i64 v) {
    if (!x || l == r) return calc(t[x].k, t[x].b, v);
    i64 mid = l + r >> 1;
    return min(calc(t[x].k, t[x].b, v), mid < v ? query(rc(x), mid + 1, r, v) : query(lc(x), l, mid, v));
}

void solve() {
    idx = 0;
    int n, m;
    cin >> n >> m;
    vector<vector<array<i64, 3>>> e1(n + 1), e2(n + 1);
    vector<array<i64, 4>> edges(m);

    i64 R = 1e9;

    for (auto& [u, v, t, w] : edges) {
        cin >> u >> v >> t >> w;
        e1[u].push_back({v, t, w});
        e2[v].push_back({u, t, w});
        R = min(R, t / w);
    }

    vector<i64> dis1(n + 1, 1e18), dis2(n + 1, 1e18);

    auto dijkstra = [&](auto& dis, auto& e, int s) {
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<>> q;
        q.emplace(0, s);
        dis[s] = 0;
        while (q.size()) {
            auto [d, u] = q.top();
            q.pop();
            if (d > dis[u]) continue;
            for (auto [v, t, w] : e[u]) {
                if (dis[v] > d + t) {
                    dis[v] = d + t;
                    q.emplace(dis[v], v);
                }
            }
        }
    };

    dijkstra(dis1, e1, 1);
    dijkstra(dis2, e2, n);

    int root = 0;

    for (auto [u, v, t, w] : edges) {
        modify(root, 1, R, -w, t + dis1[u] + dis2[v]);
    }

    int q;
    cin >> q;

    vector<int> queries(q);
    while (q--) {
        i64 k;
        cin >> k;
        cout << query(root, 1, R, k) << "\n";
    }
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

D Donkey Thinks…

比较有技巧的DP。很明显是一个背包，但是价值不方便计算。考虑枚举选中总物品的体积S，这样价值就变为定值，对每个体积S计算选中物品体积恰好是S的最大价值。直接做复杂度会爆，考虑优化。注意到对于体积为v的物品而言，最多选S/v个。那么只计算价值最大的前S/v个即可。这样总数量是调和级数的复杂度，也就是VlogV。选价值最大的这一步可以使用nth_element，复杂度是线性。对每个S都是O(n+V^2logV)，总复杂度O(nV+V3logV)。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, V;
    cin >> n >> V;
    vector<vector<tuple<i64, i64>>> a(V + 1);
    for (int h, s, d, i = 1; i <= n; ++i) {
        cin >> h >> s >> d;
        a[s].emplace_back(h, d);
    }
    vector<i64> dp(V + 1);
    for (int S = V; S >= 0; --S) {
        vector<bool> flag(S + 1);
        flag[0] = 1;
        for (int i = 1; i <= S; ++i) dp[i] = -1e18;
        for (int i = 1; i <= S; ++i) {
            int k = min((int)a[i].size(), S / i);
            nth_element(a[i].begin(), a[i].begin() + k, a[i].end(), greater());
            for (auto [h, d] : a[i] | std::views::take(k)) {
                for (int j = S; j >= i; --j) {
                    if (!flag[j - i]) continue;
                    dp[j] = max(dp[j], dp[j - i] + h);
                    flag[j] = 1;
                }
            }
        }
        for (auto& p : a) {
            for (auto& [h, d] : p) {
                h -= d;
            }
        }
    }
    //for (int i = 0; i <= V; ++i) cout << dp[i] << " \n"[i == V];
    cout << ranges::max(dp) << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/