PROBLEM LINK:
Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- Abhishek Pandey
DIFFICULTY:
MEDIUM-HARD
PRE-REQUISITES:
Segment Tree + Lazy Propagation, Dynamic Programming, DP on Trees, Euler Tour of Tree
PROBLEM:
Batman starts from vertex u. At each second, he can choose to catch a robber whose power is strictly less than his’. Also, the path of robber must lie COMPLETELY inside the path of batman from his current vertex to the chosen vertex. His power then increases by t. We need to find maximal achievable power of batman if he catches robbers optimally.
QUICK EXPLANATION:
Key to AC- This question was a test of DP on trees along with Segment Tree and Lazy Propagation. Practice of such questions was the key.
Let dp[v] be the maximum power obtained if we are at vertex v. We use segment tree along with lazy propagation to update and maintain the table. We narrow down the solution to 3 cases-
- When u is parent of v
- When v is parent of u
- Neither of above holds
We can easily obtain the range of update using Euler Tour of the tree and examining cases when its possible for batman to choose an appropriate vertex g to catch robber, and when not.
EXPLANATION:
This was the hardest problem of the set. It is expected that the pre-requisites are clear. The editorial will have 4 segments (please get the pun), one for pre-calculations done, one discussing the segment tree, other handling updates and lazy propagation along with case analysis, and last one DP. @mgch (tester’s) solution will be referred to implementation.
1. Pre-calculations-
We intitialize the dp table with -\infty initially, and do a DFS for Euler tour of tree. Euler Tour will store the time when we enter a node and its sub-tree (in in[u]), and when we exit it (in out[u]).
We initialise the dp table by setting dp[s]=p where s is the starting vertex and p is initial power of Batman.
2. Building Segment Tree-
What do we store in node? As said earlier, the tree is built on array dp[], so in each node (say tree[v]) we will store answer (i.e. max(dp[l..r]), or more formally-
- if l==r: tree[v] = dp[l];
- else tree[v]=max(tree[2v], tree[2v+1]);
Code for building the tree is in tab below. Compare it with what you can come up with after reading the explanation!
Click to view
void build(int v, int l, int r) {
if (l != r) {
build(v + v, l, (l + r) / 2);
build(v + v + 1, (l + r) / 2 + 1, r);//Build Child nodes first
tr[v] = max(tr[v + v], tr[v + v + 1]);
} else {
tr[v] = dp[l];
}
add[v] = -1LL << 60;//Used in lazy propagation. Can ignore right now. Just initializing this
//array.
}
3. Query, Update and Lazy Propagation-
We must keep the following condition in mind-
Let's denote Batman's current vertex by s (s=si initially). To catch the robber, Batman must choose a vertex g such that each vertex on the simple path between x and y (inclusive) lies also on the simple path between s and g (inclusive). If it is impossible to choose a vertex g so that this condition is satisfied, Batman cannot catch this robber.
Lets analyze it in light of 3 cases analyzed in Quick Explanation Section. Let me refer to x and y as u and v respectively as its more conventional :).
- u is parent of v- To catch this robber, Batman must NOT be at a node which allows entry inside the simple path (from u to v) from points other than u and v. Else he will not be able to cover ALL nodes in simple path from u to v. (If it is possible to catch the robber, we will update value of dp table at ALL nodes from where Batman can chose an appropriate vertex g. To formalize, we will update all nodes where batman can choose a destination, i.e. sub-tree of v if a destination can be chosen there, or everything outside sub-tree of w (w=u's first son lying in path from u to v) if an appropriate destination can be chosen…
- If v is parent of u. - Dealt exactly same as above.
- Neither of above holds \implies Both have a common parent. Hence we can go from sub-tree of u to sub-tree of v and vice-versa. Both these sub-trees must be updated.
In above, remember that the vertices of destination are updated! Recall what are we storing in dp[v]. “Let dp[v] be the maximum power obtained if we are at vertex v.”
The “syntax” to query is given below (i.e. how to call query function + Case analysis).See if it matches with what you understood!
Click to view
int u, v, r, t;
scanf("%d%d%d%d", &u, &v, &r, &t);
//possible 3 cases:
r++;
//1: u is parent of v in DFS-order, then we need to try to update
//the DP for Batman from nodes that are up on u and sons of u that
//aren't parents of v -> (subtree v)
//(subtree v) -> (the tree above u, u and sons of u that aren't parents of v)
//thes segments are continuous in the DFS-order, we can apply segment tree with lazy propagation
//for the next function A[x] = max(A[x], Value), X = L..R
if (isPar(u, v)) {//u is parent of v.
int w = getPar(v, u);
long long X = max(get(1, 1, n, 1, in[w] - 1), get(1, 1, n, out[w] + 1, n));
//From before entering u's sub-tree or after coming out of u's sub-tree
long long Y = get(1, 1, n, in[v], out[v]);//From V's subtree
if (X >= r) {
upd(1, 1, n, in[v], out[v], X + t);//We end up in v's subtree
}
if (Y >= r) {
upd(1, 1, n, 1, in[w] - 1, Y + t);//Can land up in or out of
upd(1, 1, n, out[w] + 1, n, Y + t);//u's sub-tree. Both must be
//updated.
}
} else if (isPar(v, u)) { // V is parent of U
//Absolutely similar case to the case of above
//Cause the direction doesn't matter
int w = getPar(u, v);//Do on your own for this half!
long long X = get(1, 1, n, in[u], out[u]);
long long Y = max(get(1, 1, n, 1, in[w] - 1), get(1, 1, n, out[w] + 1, n));
if (X >= r) {
upd(1, 1, n, 1, in[w] - 1, X + t);
upd(1, 1, n, out[w] + 1, n, X + t);
}
if (Y >= r) {
upd(1, 1, n, in[u], out[u], Y + t);
}
} else { //The easiest case
//U isn't parent of V and V isn't parent of U
//Batman can go only from
//(subtree u) -> (subtree v)
//(subtree v) -> (subtree u)
//and reclalculating DP:
long long X = get(1, 1, n, in[u], out[u]);
long long Y = get(1, 1, n, in[v], out[v]);//Check comments above :)
if (X >= r) {
upd(1, 1, n, in[v], out[v], X + t);
}
if (Y >= r) {
upd(1, 1, n, in[u], out[u], Y + t);//dp[v]==>Destination. Remember!
}
}
With that clear, how do we exactly query? Thats even easier! Recall the standard query functions. The only change here is that we a re doing lazy propagation right now. Lets analyze what will be the cases/steps in query function.
- If out of range, return -\infty
- Update the node if needed.
- If it lies completely in range, return the node.
- If not in range, query in ranges [L,Mid] and [Mid+1,R] and return the maximum obtained answer. Make sure to push updates/do lazy updates before getting answer!
Click to view
long long get(int v, int L, int R, int l, int r) {
if (l > r) {//Out of range or invalid range
return -1LL << 60;
}
tr[v] = max(tr[v], add[v]);//Update the node.
push(v, L, R);//Push updates to children
if (L == l && r == R) {//Completely in the range
return tr[v];
}
int M = (L + R) / 2;
push(v, L, R);
if (r <= M) {//Query right child if left child out of range
push(v + v + 1, M + 1, R);//Update child before querying
return get(v + v, L, M, l, r);
}
if (l > M) {//Query left child if right child out of range
push(v + v, L, M);
return get(v + v + 1, M + 1, R, l, r);
}
return max(get(v + v, L, M, l, M), get(v + v + 1, M + 1, R, M + 1, r));
}
For reference, tester’s implementation of push function is given below-
Click to view
void push(int v, int L, int R) {
if (L != R) {//Update children of v
add[v + v] = max(add[v + v], add[v]);//add[v] is an array to store lazy updates.
add[v + v + 1] = max(add[v + v + 1], add[v]);
}
tr[v] = max(tr[v], add[v]);//Update leaf
}
The only thing left is now update function. I think if you’ve read my previous segment tree editorials, it must be getting like “Something is repeating again and again.” Yes! Thats the first sign of improvement! Try to make the update function on your own w.r.t. given query functions and syntax. A commented version is given in tabs below-
Click to view
void upd(int v, int L, int R, int l, int r, long long val) {
if (l > r) {//Invalid range
return;
}
push(v, L, R);//push lazy update
if (L == l && r == R) {
add[v] = max(add[v], val);//add[v] is an array to store lazy updates.
push(v, L, R);//Push lazy updates
return;
}
int M = (L + R) / 2;
push(v, L, R);
if (r <= M) {//Refer to query function
upd(v + v, L, M, l, r, val);//Push lazy updates to one and update required child
push(v + v + 1, M + 1, R);
} else if (l > M) {
push(v + v, L, M);//Push update to the child which wont be traversed any more
upd(v + v + 1, M + 1, R, l, r, val);//Traverse the other child
} else {
upd(v + v, L, M, l, M, val);//Remember leaves must be updated first
upd(v + v + 1, M + 1, R, M + 1, r, val);
}
tr[v] = max(tr[v + v], tr[v + v + 1]);
tr[v] = max(tr[v], add[v]);//Update and lazy update the node.
}
4. Dynamic Programming-
Finished.
??
???
??????????
What?
Dynamic Programming says “Remember previous values” and I say “Remember the previous explanation.” :p. how many of you noticed that this part is already discussed in 3 segments above? Some exclusive parts were, in finding LCA of the two nodes u and v (Refer to link in pre-requisites) and our segment tree :).
SOLUTION:
The setter and tester’s code are given below. If the links dont work, please view code in the “View content” tab. I pasted code their only for your comfort :). Tester’s code is commented and discussed in editorial.
Click to view
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
///#define int long long
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
///---program start---///
ll inf=1e18;
/// segment tree of maximums in segment with range updates
struct segment_tree
{
int n;
vector<ll> t;
vector<ll> push;
segment_tree()
{
n=0;
t.clear();
push.clear();
}
segment_tree(int n)
{
this->n=n;
t.assign(4*n+10,-inf);
push.assign(4*n+10,-inf);
}
void make_push(int v)
{
if (push[v]==-inf){
return;
}
t[v*2]=max(t[v*2],push[v]);
t[v*2+1]=max(t[v*2+1],push[v]);
push[v*2]=max(push[v*2],push[v]);
push[v*2+1]=max(push[v*2+1],push[v]);
push[v]=-inf;
}
void upd(int v,int l,int r,int tl,int tr,ll val)
{
if (l>tr||r<tl||tl>tr){
return;
}
if (l>=tl&&r<=tr){
t[v]=max(t[v],val);
push[v]=max(push[v],val);
return;
}
make_push(v);
int m=(l+r)/2;
upd(v*2,l,m,tl,tr,val);
upd(v*2+1,m+1,r,tl,tr,val);
t[v]=max(t[v*2],t[v*2+1]);
}
ll get(int v,int l,int r,int tl,int tr)
{
if (l>tr||r<tl||tl>tr){
return -inf;
}
if (l>=tl&&r<=tr){
return t[v];
}
make_push(v);
int m=(l+r)/2;
return max(
get(v*2,l,m,tl,tr),
get(v*2+1,m+1,r,tl,tr)
);
}
ll get(int l,int r)
{
if (l<=r){
return get(1,1,n,l,r);
}
else{
return max(
get(1,1,n,1,r),
get(1,1,n,l,n)
);
}
}
void upd(int l,int r,ll val)
{
if (l<=r){
upd(1,1,n,l,r,val);
}
else{
upd(1,1,n,1,r,val);
upd(1,1,n,l,n,val);
}
}
};
#define arr (int)(1e6+10)
int tin[arr];
int tout[arr];
int T;
vi reb[arr];
const int M=20;
int p[arr][M];
void dfs1(int v,int pred)
{
p[v][0]=pred;
for (int i=1;i<M;i++){
p[v][i]=p[p[v][i-1]][i-1];
}
tin[v]=++T;
for (auto wh:reb[v]){
if (wh!=pred){
dfs1(wh,v);
}
}
tout[v]=T;
}
/// return next vertex after u in simple path (u,v)
bool is_pred(int u,int v) /// u is pred v
{
return tin[u]<=tin[v]&&tout[u]>=tout[v];
}
int n,S,P;
segment_tree ST;
int get_next(int u,int v) /// u is pred v
{
for (int i=M-1;i>=0;i--){
if (is_pred(u,p[v][i])&&u!=p[v][i]){
v=p[v][i];
}
}
return v;
}
void upd_way(int u,int v,ll r,ll t)
{
if (is_pred(u,v)){ /// trivial :)
ll val1=ST.get(tin[v],tout[v]);
int kek=get_next(u,v);
ll val2=ST.get(tout[kek]+1,tin[kek]-1);
if (val1>r){
val1+=t;
ST.upd(tout[kek]+1,tin[kek]-1,val1);
}
if (val2>r){
val2+=t;
ST.upd(tin[v],tout[v],val2);
}
}
elif (is_pred(v,u)){ /// trivial :)
swap(u,v);
ll val1=ST.get(tin[v],tout[v]);
int kek=get_next(u,v);
ll val2=ST.get(tout[kek]+1,tin[kek]-1);
if (val1>r){
val1+=t;
ST.upd(tout[kek]+1,tin[kek]-1,val1);
}
if (val2>r){
val2+=t;
ST.upd(tin[v],tout[v],val2);
}
}
else{ /// trivial :)
ll val1=ST.get(tin[v],tout[v]);
ll val2=ST.get(tin[u],tout[u]);
if (val1>r){
val1+=t;
ST.upd(tin[u],tout[u],val1);
}
if (val2>r){
val2+=t;
ST.upd(tin[v],tout[v],val2);
}
}
}
void debug()
{
for (int i=1;i<=n;i++){
cout<<ST.get(tin[i],tin[i])<<" ";
}
cout<<"\n";
cout<<string(20,'-')<<"\n";
}
void solve()
{
cin>>n>>S>>P;
for (int i=1;i<=n;i++){
reb[i].clear();
}
T=0;
for (int i=1;i<n;i++){
int u,v;
cin>>u>>v;
reb[u].pb(v);
reb[v].pb(u);
}
dfs1(1,1);
ST=*new segment_tree(n);
ST.upd(tin[S],tin[S],P); /// init dp
int m;
cin>>m;
while (m--){
ll u,v,r,t;
cin>>u>>v>>r>>t;
upd_way(u,v,r,t);
// debug();
}
cout<<ST.get(1,n)<<"\n"; /// get max value of all vertex
}
main()
{
#ifdef I_love_Maria_Ivanova
files("barik");
freopen("debug.txt","w",stderr);
#endif
fast;
int test;
cin>>test;
while (test--){
solve();
}
}
Click to view
#include <bits/stdc++.h>
using namespace std;
const int MaxN = (int)4e5 + 10;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const int MaxL = 19;
int n, in[MaxN], out[MaxN];
int timer, s, p, m, up[MaxN][MaxL];
vector < int > g[MaxN];
long long dp[MaxN];
long long tr[4 * MaxN], add[4 * MaxN];
void dfs(int v, int p) {
in[v] = ++timer;
up[v][0] = p;
for (int i = 1; i < MaxL; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int i = 0; i < (int)g[v].size(); ++i) {
int to = g[v][i];
if (to == p) {
continue;
}
dfs(to, v);
}
out[v] = timer;
}
bool isPar(int u, int v) {
return in[u] <= in[v] && out[v] <= out[u];
}
int getPar(int u, int v) {
for (int i = MaxL - 1; i >= 0; --i) {
if (up[u][i] != v && isPar(v, up[u][i])) {
u = up[u][i];
}
}
return u;
}
void push(int v, int L, int R) {
if (L != R) {
add[v + v] = max(add[v + v], add[v]);
add[v + v + 1] = max(add[v + v + 1], add[v]);
}
tr[v] = max(tr[v], add[v]);
}
void upd(int v, int L, int R, int l, int r, long long val) {
if (l > r) {
return;
}
push(v, L, R);
if (L == l && r == R) {
add[v] = max(add[v], val);
push(v, L, R);
return;
}
int M = (L + R) / 2;
push(v, L, R);
if (r <= M) {
upd(v + v, L, M, l, r, val);
push(v + v + 1, M + 1, R);
} else if (l > M) {
push(v + v, L, M);
upd(v + v + 1, M + 1, R, l, r, val);
} else {
upd(v + v, L, M, l, M, val);
upd(v + v + 1, M + 1, R, M + 1, r, val);
}
tr[v] = max(tr[v + v], tr[v + v + 1]);
tr[v] = max(tr[v], add[v]);
}
long long get(int v, int L, int R, int l, int r) {
if (l > r) {
return -1LL << 60;
}
tr[v] = max(tr[v], add[v]);
push(v, L, R);
if (L == l && r == R) {
return tr[v];
}
int M = (L + R) / 2;
push(v, L, R);
if (r <= M) {
push(v + v + 1, M + 1, R);
return get(v + v, L, M, l, r);
}
if (l > M) {
push(v + v, L, M);
return get(v + v + 1, M + 1, R, l, r);
}
return max(get(v + v, L, M, l, M), get(v + v + 1, M + 1, R, M + 1, r));
}
void build(int v, int l, int r) {
if (l != r) {
build(v + v, l, (l + r) / 2);
build(v + v + 1, (l + r) / 2 + 1, r);
tr[v] = max(tr[v + v], tr[v + v + 1]);
} else {
tr[v] = dp[l];
}
add[v] = -1LL << 60;
}
void solve() {
scanf("%d%d%d", &n, &s, &p);
for (int i = 1; i <= n; ++i) {
dp[i] = -1LL << 60;
}
for (int i = 0; i < n - 1; ++i) {
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0); //we need to know in[v]..out[v] for every node, it really simplifies the solution for current problem
dp[in[s]] = p; //using DFS-order, dp[v] contains in dp[in[v]]
build(1, 1, n); //building the segment tree for DP
scanf("%d", &m);
for (int it = 0; it < m; ++it) {
int u, v, r, t;
scanf("%d%d%d%d", &u, &v, &r, &t);
//possible 3 cases:
r++;
//1: u is parent of v in DFS-order, then we need to try to update
//the DP for Batman from nodes that are up on u and sons of u that
//aren't parents of v -> (subtree v)
//(subtree v) -> (the tree above u, u and sons of u that aren't parents of v)
//thes segments are continuous in the DFS-order, we can apply segment tree with lazy propagation
//for the next function A[x] = max(A[x], Value), X = L..R
if (isPar(u, v)) {
int w = getPar(v, u);
long long X = max(get(1, 1, n, 1, in[w] - 1), get(1, 1, n, out[w] + 1, n));
long long Y = get(1, 1, n, in[v], out[v]);
if (X >= r) {
upd(1, 1, n, in[v], out[v], X + t);
}
if (Y >= r) {
upd(1, 1, n, 1, in[w] - 1, Y + t);
upd(1, 1, n, out[w] + 1, n, Y + t);
}
} else if (isPar(v, u)) { // V is parent of U
//Absolutely similar case to the case of above
//Cause the direction doesn't matter
int w = getPar(u, v);
long long X = get(1, 1, n, in[u], out[u]);
long long Y = max(get(1, 1, n, 1, in[w] - 1), get(1, 1, n, out[w] + 1, n));
if (X >= r) {
upd(1, 1, n, 1, in[w] - 1, X + t);
upd(1, 1, n, out[w] + 1, n, X + t);
}
if (Y >= r) {
upd(1, 1, n, in[u], out[u], Y + t);
}
} else { //The easiest case
//U isn't parent of V and V isn't parent of U
//Batman can go only from
//(subtree u) -> (subtree v)
//(subtree v) -> (subtree u)
//and reclalculating DP:
long long X = get(1, 1, n, in[u], out[u]);
long long Y = get(1, 1, n, in[v], out[v]);
if (X >= r) {
upd(1, 1, n, in[v], out[v], X + t);
}
if (Y >= r) {
upd(1, 1, n, in[u], out[u], Y + t);
}
}
}
for (int i = 1; i <= n; ++i) {
g[i].clear();
}
//outputting the maximal value over all dp[v]
cout << max(tr[1], add[1]) << "\n";
timer = 0;
}
int main() {
// freopen("input.txt", "r", stdin);
int t;
scanf("%d", &t);
// t = 10;
while (t --> 0) {
solve();
}
return 0;
}
Editorialist Solution will be put on demand 
Time Complexity=O(MlogN)
CHEF VIJJU’S CORNER 
1. Give a brief note on uses of Euler Tour in Competitive coding! EXPLORE!! (25 karma for decent answer ). [I can myself give notes, but I want you guys to explore and contribute as well. )
2. Author’s Solution- He worked hard to write it and hoped you love it!!
Click to view
ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA $dp[v]=max($Є$ТЬСЯ,ЬСЯ)$ ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТЬСЯVYTʹSYAВИ ВИПУСКАЄТЬСЯVYИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТ$u,v$ ИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТИПУСКАЄТЬСЯVY VYPUSKAYETʹSYAВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYA ВИ ВИПУСКАЄТЬСЯVY VYPUSKAYETʹSYATʹSYAВИ ВИПУСКАЄТ
3. ???
Click to view
Let’s read in [v], out [v] as the input and output time in the tree’s traversal. We will maintain online dp [v] - the maximum force that can be obtained if we are at the vertex v. Initially, dp [i] = - inf, i\neq S; dp [s] = p.
To update dp, you need to find a maximum of dp in no more than two segments. Let it be equal to m_x. If m_x> r, then you need to update the values of dp also at no more than two segments through m_x + t. Under the segments we mean the set of vertices for which they in [i] form a continuous interval of numbers. To do this, you can use a tree of segments with a lazy push. Complexity O (m * log (n)).
4. Test case Bank-
Click to view
No small test case used in this problem. Please give WA solutions for analysis. Request to community to add TCs here as well for reference
One of the small test case by setter-
Test:
1
6 1 4
1 2
2 3
2 4
4 5
1 6
5
6 4 3 8
1 2 3 2
4 6 5 -1
6 5 4 6
5 4 5 -3
Answer:
12
5. Related Problems-