Since it’s guaranteed that each queried $v$ exists, this problem is not necessarily online.
First construct the entire tree, and then DP on the tree.
For each vertex, maintain two values, $minv$ and $maxv$, representing the minimum and maximum sums of the substring of the path from the root to this vertex.
Transition function:
$dpmax[i] = max(x, dpmax[v] + x)$
$dpmin[i] = min(x, dpmin[v] + x)$
Time complexity $O(n)$
Actually, this problem is a easy version, where the queries do not have to start from the root; they can be between any two vertices.
If it’s between any two vertices, first construct the entire tree, with each vertex storing the timestamp it was added and its weight.
Preprocess three arrays:
ancestor[i][j] represents the $2^j-th$ ancestor of vertex $i$
maxv[i][j] represents the maximum value of the path from vertex $i$ to its $2^j-th$ ancestor
minv[i][j] represents the minimum value of the path from vertex $i$ to its $2^j-th$ ancestor
Then preprocess the DP array. For each query, increase both vertex upwards by powers of two to find the answer. The complexity is $O(n\log)$.
For the harder version, another approach is heavy-light decomposition, with a complexity of $O(n\log^2)$. If require online, Link-Cut Tree is a solution.
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
void solve() {
int q; cin >> q;
int idx = 0;
// min, max
vector<pair<int, int>> dp(q + 10, {INF, -INF}), num(q + 10);
dp[idx] = {1, 1};
num[idx] = {0, 1};
while (q--) {
string s; cin >> s;
if (s[0] == '+') {
int v, x; cin >> v >> x; --v;
dp[++idx] = {min(x, dp[v].first + x), max(x, dp[v].second + x)};
num[idx] = {min(num[v].first, dp[idx].first), max(num[v].second, dp[idx].second)};
// debug(v, x, dp[idx], num[idx])
}
else if (s[0] == '?') {
int u, v, x; cin >> u >> v >> x; --u, --v;
cout << (x >= num[v].first && x <= num[v].second ? "YES" : "NO") << endl;
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
Alright, so keobet88 showed up on my radar. Checked it out and the interface is clean. Seems reliable for kèo. What do you guys think?
55winvip, that’s where the real money is at! It’s the VIP experience, try it. It’s the only place where it is! See you at 55winvip.
9nbetcom, huh? Took it for a spin. Honestly, it’s pretty smooth. Good selection and easy to use! Seems solid. Play responsibly though, yeah? 9nbetcom
Yo, 66ggplataforma is where it’s at! Been having a blast. Check it out here: 66ggplataforma
Alright, checking out 515bet5. Heard mixed things, but I gave it a go. Site’s clean and mobile-friendly, which is a plus. Gameplay’s smooth. Worth a look if you need something new. See for yourself: 515bet5.
Heard 661betvip is trying to step up their game. The VIP program looks interesting if you’re a high roller. Might be worth a shot if you’re looking for some extra perks. Check out what they’re offering: 661betvip.
Roulette strategy is fascinating – probability & risk are key! Seeing platforms like 747 live com expand options in the Asian market is interesting, especially with their focus on secure, accessible gaming experiences. It’s good to see responsible gaming prioritized.
Pattern recognition is key in baccarat, but a smooth mobile experience matters too! Platforms like the jl 3 app casino are streamlining access for Filipino players – quick loading & easy navigation are huge wins. It’s about convenience and strategy!