# Invitation to CodeChef April Lunchtime 2020

We invite you to participate in CodeChef’s April Lunchtime, this Saturday, 25th April, from 7:30 pm to 10:30 pm IST.
3 hours, 5 problems.

We will also be hosting two live problem discussion sessions on Sunday (26th) from 5pm to 6:30pm IST (first 4 problems) and on Monday (27th) from 5pm to 6:30pm IST (last 3 problems), where our panelist, rajarshi_basu will discuss the Lunchtime problems. Find more details here.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef’s contests, you can share them here.

Joining me on the problem setting panel are:

Prizes:

Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

4 Likes

My problems are not appearing. Help!

Hi all
I hope you guys had a nice contest. The editorials for first six problems are ready and would be available in some time.

Posting basic idea for last problem below.

JMPFEVER

Suppose we want to compute f(u, v) such that the path is u = a_1, a_2 \ldots a_L = v and LCA is a_k. f(u,v) = \sum_{i = 1}^L i*W_i can be written as \sum_{i = 1}^k i*W_i + k*\sum_{i = k+1}^L W_i + \sum_{i = k+1}^{L} i*W_i

Consider a pair (k, \sum_{i = 1}^k i*W_i) and pair (\sum_{i = k+1}^L W_i, \sum_{i = k+1}^{L} i*W_i), the combination of this pair is a valid path. Also, it is of the form convex hull optimization.

Suppose we for each node u in the tree, we want to find the maximum score of trip starting somewhere in subtree of u and ending at u. Calling this UP_u

Similarly, we want the maximum score of the trip starting from u and ending somewhere in subtree of u. Calling this DOWN_u

We can compute both using dsu on tree trick

After that, we need to use dsu on tree and convex hull trick again, while handling offsets to avoid rebuilding hull at each node and instead using heavy child’s hull.

Will post detailed editorial as soon as possible.

Setter's Solution
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <cstring>
#include <iostream>
#define pie acos(-1)
#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sl(a) scanf("%lld",&a)
#define sll(a,b) scanf("%lld %lld",&a,&b)
#define slll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define ss(st) scanf("%s",st)
#define sch(ch) scanf("%ch",&ch)
#define ps(a) printf("%s",a)
#define newLine() printf("\n")
#define pi(a) printf("%d",a)
#define pii(a,b) printf("%d %d",a,b)
#define piii(a,b,c) printf("%d %d %d",a,b,c)
#define pl(a) printf("%lld",a)
#define pll(a,b) printf("%lld %lld",a,b)
#define plll(a,b,c) printf("%lld %lld %lld",a,b,c)
#define pch(c) printf("%ch",c)
#define debug1(str,a) printf("%s=%d\n",str,a)
#define debug2(str1,str2,a,b) printf("%s=%d %s=%d\n",str1,a,str2,b)
#define debug3(str1,str2,str3,a,b,c) printf("%s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c)
#define debug4(str1,str2,str3,str4,a,b,c,d) printf("%s=%d %s=%d %s=%d %s=%d\n",str1,a,str2,b,str3,c,str4,d)
#define for0(i,n) for(i=0;i<n;i++)
#define for1(i,n) for(i=1;i<=n;i++)
#define forab(i,a,b) for(i=a;i<=b;i++)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define nl puts("")
#define sd(a) scanf("%lf",&a)
#define sdd(a,b) scanf("%lf %lf",&a,&b)
#define sddd(a,b,c) scanf("%lf %lf %lf",&a,&b,&c)
#define sp printf(" ")
#define ll long long int
#define ull unsigned long long int
#define MOD 1000000007
#define mpr make_pair
#define pub(x) push_back(x)
#define pob(x) pop_back(x)
#define mem(ara,value) memset(ara,value,sizeof(ara))
#define INF INT_MAX
#define eps 1e-9
#define checkbit(n, pos) (n & (1<<pos))
#define setbit(n, pos) (n  (1<<pos))
#define para(i,a,b,ara)\
for(i=a;i<=b;i++){\
if(i!=0){printf(" ");}\
cout<<ara[i];\
}\
printf("\n");
#define pvec(i,vec)\
for(i=0;i<vec.size();i++){\
if(i!=0){printf(" ");}\
cout<<vec[i];\
}\
printf("\n");
#define ppara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
for(j=0;j<m;j++){\
if(j!=0){printf(" ");}\
cout<<ara[i][j];\
}\
printf("\n");\
}
#define ppstructara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<m;j++){\
cout<<ara[i][j];printf("\n");\
}\
}
#define ppvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:",i);\
for(j=0;j<vec[i].size();j++){\
if(j!=0){printf(" ");}\
cout<<vec[i][j];\
}\
printf("\n");\
}
#define ppstructvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:",i);\
for(j=0;j<vec[i].size();j++){\
cout<<vec[i][j];printf("\n");\
}\
}
#define sara(i,a,b,ara)\
for(i=a;i<=b;i++){\
scanf("%d",&ara[i]);\
}
#define pstructara(i,a,b,ara)\
for(i=a;i<=b;i++){\
cout<<ara[i];nl;\
}
#define pstructvec(i,vec)\
for(i=0;i<vec.size();i++){\
cout<<vec[i];nl;\
}
#define pstructstl(stl,x)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
x=*it;\
cout<<x;nl;\
}\
nl;
#define pstl(stl)\
for(__typeof(stl.begin()) it=stl.begin();it!=stl.end();++it){\
if(it!=stl.begin()){sp;}\
pi(*it);\
}\
nl;
#define ppairvec(i,vec)\
for(i=0;i<vec.size();i++){\
cout<<vec[i].first;sp;cout<<vec[i].second;printf("\n");\
}
#define ppairara(i,a,b,ara)\
for(i=a;i<=b;i++){\
cout<<ara[i].first;sp;cout<<ara[i].second;printf("\n");\
}
#define pppairvec(i,j,n,vec)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<vec[i].size();j++){\
cout<<vec[i][j].first;sp;cout<<vec[i][j].second;nl;\
}\
}
#define pppairara(i,j,n,m,ara)\
for(i=0;i<n;i++){\
printf("%d:\n",i);\
for(j=0;j<m;j++){\
cout<<ara[i][j].first;printf(" ");cout<<ara[i][j].second;nl;\
}\
}
#define SZ 2 * 100010
#define xx first
#define yy second
using namespace std;
//using namespace __gnu_pbds;
//bool status[100010];
//vector <int> prime;
//void siv(){
//    int N = 100005, i, j; prime.clear();
//    int sq = sqrt(N);
//    for(i = 4; i <= N; i += 2){ status[i] = true; }
//    for(i = 3; i <= sq; i+= 2){
//        if(status[i] == false){
//            for(j = i * i; j <= N; j += i){ status[j] = true; }
//        }
//    }
//    status[1] = true;
//    for1(i, N){ if(!status[i]){ prime.pub(i); } }
//}
//auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
//std::mt19937 mt(seed);
inline int add(int _a, int _b){
if(_a < 0){ _a += MOD; }
if(_b < 0){ _b += MOD; }
if(_a + _b >= MOD){ return _a + _b - MOD; }
return _a + _b;
}
inline int mul(int _a, int _b){
if(_a < 0){ _a += MOD; }
if(_b < 0){ _b += MOD; }
return ((ll)((ll)_a * (ll)_b)) % MOD;
}
const long long LL_INF = (long long) 2e18 + 5;
struct point {
long long x, y;
point() : x(0), y(0) {}
point(long long _x, long long _y) : x(_x), y(_y) {}
};
// dp_hull enables you to do the following two operations in amortized O(log n) time:
// 1. Insert a pair (a_i, b_i) into the structure
// 2. For any value of x, query the maximum value of a_i * x + b_i
// All values a_i, b_i, and x can be positive or negative.

//max_cost(u, v) = pd[u] + jump_cost(u, v) + dp[v]
//= pd[u] + (ur[u] - ur[p) - (dpt[u] - dpt[lca] + 1) * sum[p + (sum[v] - sum[lca]) * (dpt[u] - dpt[lca] + 1)
//+ (ru[v] - ru[lca]) - (sum[v] - sum[lca]) * dpt[lca] + dp[v]
//= pd[u] + (ur[u] - ur[p) - (dpt[u] - dpt[lca] + 1) * sum[p - sum[lca] * (dpt[u] - dpt[lca] + 1) - ru[lca] + sum[lca] * dpt[lca]
//+ ru[v] + dp[v] + sum[v] * (dpt[u] - 2 * dpt[lca] + 1){c = ru[v] + dp[v], m = sum[v], x = (dpt[u] - 2 * dpt[lca] + 1)}

//max_cost(u, lca, v) = pd[u] + jump_cost(u, lca) + jump_cost(lca, v) + dp[v]
//= pd[u] + (ur[u] - ur[p) - (dpt[u] - dpt[lca] + 1) * sum[p]
//+ (ru[v] - ru[p) - (sum[v] - sum[p) * (dpt[lca] - 1) + dp[v]
//= pd[u] + (ur[u] - ur[p) - (dpt[u] - dpt[lca] + 1) * sum[p - ru[p + sum[p * (dpt[lca] - 1)
//+ ru[v] + dp[v] + sum[v] * (-dpt[lca] + 1)

//max_cost(v, u) = pd[v] + jump_cost(v, u) + dp[u]
//= pd[v] + (ur[v] - ur[p) - (dpt[v] - dpt[lca] + 1) * sum[p + (sum[u] - sum[lca]) * (dpt[v] - dpt[lca] + 1)
//+ (ru[u] - ru[lca]) - (sum[u] - sum[lca]) * dpt[lca] + dp[u]
//= (ru[u] - ru[lca]) - (sum[u] - sum[lca]) * dpt[lca] + dp[u] - ur[p + (dpt[lca] - 1) * sum[p + (sum[u] - sum[lca]) * (- dpt[lca] + 1)
//+ pd[v] + ur[v] + dpt[v] * (sum[u] - sum[lca] - sum[p){c = pd[v] + ur[v], m = dpt[v], x = (sum[u] - sum[lca] - sum[p)}

//max_cost(v, lca, u) = pd[v] + jump_cost(v, lca) + jump_cost(lca, u) + dp[u]
//= pd[v] + (ur[v] - ur[p) - (dpt[v] - dpt[lca] + 1) * sum[p
//+ (ru[u] - ru[p) - (sum[u] - sum[p) * (dpt[lca] - 1) + dp[u]
//= (ru[u] - ru[p) - (sum[u] - sum[p) * (dpt[lca] - 1) + dp[u] - ur[p + (dpt[lca] - 1) * sum[p
// + pd[v] + ur[v] + dpt[v] * (-sum[p)
struct dp_hull {
struct segment {
point p;
mutable point next_p;
segment(point _p = {0, 0}, point _next_p = {0, 0}) : p(_p), next_p(_next_p) {}
bool operator<(const segment &other) const {
// Sentinel value indicating we should binary search the set for a single x-value.
if (p.y == LL_INF)
return p.x * (other.next_p.x - other.p.x) <= other.p.y - other.next_p.y;
return make_pair(p.x, p.y) < make_pair(other.p.x, other.p.y);
}
};
set<segment> segments;
int size() const {
return segments.size();
}
set<segment>::iterator prev(set<segment>::iterator it) const {
return it == segments.begin() ? it : --it;
}
set<segment>::iterator next(set<segment>::iterator it) const {
return it == segments.end() ? it : ++it;
}
static long long floor_div(long long a, long long b) {
return a / b - ((a ^ b) < 0 && a % b != 0);
}
static bool bad_middle(const point &a, const point &b, const point &c) {
// This checks whether the x-value where b beats a comes after the x-value where c beats b. It's fine to round
// down here if we will only query integer x-values. (Note: plain C++ division rounds toward zero)
return floor_div(a.y - b.y, b.x - a.x) >= floor_div(b.y - c.y, c.x - b.x);
}
return it != segments.begin() && next(it) != segments.end() && bad_middle(prev(it)->p, it->p, next(it)->p);
}
void insert(const point &p) {
set<segment>::iterator next_it = segments.lower_bound(segment(p));
if (next_it != segments.end() && p.x == next_it->p.x)
return;
if (next_it != segments.begin()) {
set<segment>::iterator prev_it = prev(next_it);
if (p.x == prev_it->p.x)
segments.erase(prev_it);
else if (next_it != segments.end() && bad_middle(prev_it->p, p, next_it->p))
return;
}
// Note we need the segment(p, p) here for the single x-value binary search.
set<segment>::iterator it = segments.insert(next_it, segment(p, p));
segments.erase(prev(it));
segments.erase(next(it));
if (it != segments.begin())
prev(it)->next_p = it->p;
if (next(it) != segments.end())
it->next_p = next(it)->p;
}
void insert(long long a, long long b) {
insert(point(a, b));
}
// Queries the maximum value of ax + b.
long long query(long long x) const {
assert(size() > 0);
set<segment>::iterator it = segments.upper_bound(segment(point(x, LL_INF)));
return it->p.x * x + it->p.y;
}
};
dp_hull convex, xevnoc;
const int N = 3e5;
int n, ara[N + 5], sbtr[N + 5], dpt[N + 5], vrtx[N + 5], order[N + 5], t = 0;
ll sum[N + 5], ru[N + 5], ur[N + 5], dp[N + 5], pd[N + 5];
ll global, val = 0;
void go(int u, int p, int d){
int i, j;
// pii(p, u); nl;
if(v == p) break;
sbtr[u] = 1, dpt[u] = d;
sum[u] = sum[p] + ara[u];
ru[u] = (ll)ara[u] * (ll)dpt[u] + ru[p];
ur[u] = ur[p] + sum[u];
vrtx[t++] = u, order[u] = t - 1;
for(int v : adj[u]) go(v, u, d + 1), sbtr[u] += sbtr[v];
}
//jump_cost(u, v) = (ru[v] - ru[p[u]]) - (sum[v] - sum[p[u]]) * (dpt[u] - 1)
//max_cost(u, v) = (ru[v] - ru[p[u]]) - (sum[v] - sum[p[u]]) * (dpt[u] - 1) + dp[v]
//               = -ru[p[u]] + sum[p[u]] * (dpt[u] - 1) + ru[v] + dp[v] - sum[v] * (dpt[u] - 1)
//               = -ru[p[u]] + sum[p[u]] * (dpt[u] - 1) + mx + c {m = -sum[v], x = (dpt[u] - 1), c = ru[v] + dp[v]}
//jump_cost(v, u) = (ur[v] - ur[p[u]]) - (dpt[v] - dpt[u] + 1) * sum[p[u]]
//max_cost(v, u)  = (ur[v] - ur[p[u]]) - (dpt[v] - dpt[u] + 1) * sum[p[u]] + pd[v]
//                = -ur[p[u]] + (dpt[u] - 1) * sum[p[u]] + ur[v] + pd[v] - dpt[v] * sum[p[u]]
//                =  -ur[p[u]] + (dpt[u] - 1) * sum[p[u]] + mx + c{m = -dpt[v], x = sum[p[u]], c = ur[v] + pd[v]}
void dsu_prep(int u, int p, bool keep){
int i, j, mx = -1, bg = -1;
for(int v : adj[u]) if(sbtr[v] > mx) mx = sbtr[v], bg = v;
for(int v : adj[u]) if(v != bg) dsu_prep(v, u, 0);
if(bg != -1) dsu_prep(bg, u, 1);
if(v == bg) continue;
for(i = order[v]; i <= order[v] + sbtr[v] - 1; ++i){
int x = vrtx[i];
convex.insert(-sum[x], ru[x] + dp[x]);
xevnoc.insert(-(ll)dpt[x], ur[x] + pd[x]);
}
}
dp[u] = pd[u] = 0;
dp[u] = -ru[p] + sum[p] * (ll)(dpt[u] - 1) + convex.query((ll)(dpt[u] - 1));
pd[u] = -ur[p] + sum[p] * (ll)(dpt[u] - 1) + xevnoc.query(sum[p]);
global = max(global, dp[u]), global = max(global, pd[u]);
dp[u] = max(dp[u], 0ll);
pd[u] = max(pd[u], 0ll);
}
convex.insert(-sum[u], ru[u] + dp[u]);
xevnoc.insert(-(ll)dpt[u], ur[u] + pd[u]);
if(!keep) convex.segments.clear(), xevnoc.segments.clear();
}
//max_cost(u, v) = pd[u] + jump_cost(u, v) + dp[v]
//= pd[u] + (ur[u] - ur[p]) - (dpt[u] - dpt[lca] + 1) * sum[p] + (sum[v] - sum[lca]) * (dpt[u] - dpt[lca] + 1)
//+ (ru[v] - ru[lca]) - (sum[v] - sum[lca]) * dpt[lca] + dp[v]
//= pd[u] + (ur[u] - ur[p]) - (dpt[u] - dpt[lca] + 1) * sum[p] - sum[lca] * (dpt[u] - dpt[lca] + 1) - ru[lca] + sum[lca] * dpt[lca]
//+ ru[v] + dp[v] + sum[v] * (dpt[u] - 2 * dpt[lca] + 1){c = ru[v] + dp[v], m = sum[v], x = (dpt[u] - 2 * dpt[lca] + 1)}

//max_cost(u, lca, v) = pd[u] + jump_cost(u, lca) + jump_cost(lca, v) + dp[v]
//= pd[u] + (ur[u] - ur[p]) - (dpt[u] - dpt[lca] + 1) * sum[p]
//+ (ru[v] - ru[p]) - (sum[v] - sum[p]) * (dpt[lca] - 1) + dp[v]
//= pd[u] + (ur[u] - ur[p]) - (dpt[u] - dpt[lca] + 1) * sum[p] - ru[p] + sum[p] * (dpt[lca] - 1)
//+ ru[v] + dp[v] + sum[v] * (-dpt[lca] + 1)

//max_cost(v, u) = pd[v] + jump_cost(v, u) + dp[u]
//= pd[v] + (ur[v] - ur[p]) - (dpt[v] - dpt[lca] + 1) * sum[p] + (sum[u] - sum[lca]) * (dpt[v] - dpt[lca] + 1)
//+ (ru[u] - ru[lca]) - (sum[u] - sum[lca]) * dpt[lca] + dp[u]
//= (ru[u] - ru[lca]) - (sum[u] - sum[lca]) * dpt[lca] + dp[u] - ur[p] + (dpt[lca] - 1) * sum[p] + (sum[u] - sum[lca]) * (- dpt[lca] + 1)
//+ pd[v] + ur[v] + dpt[v] * (sum[u] - sum[lca] - sum[p]){c = pd[v] + ur[v], m = dpt[v], x = (sum[u] - sum[lca] - sum[p])}

//max_cost(v, lca, u) = pd[v] + jump_cost(v, lca) + jump_cost(lca, u) + dp[u]
//= pd[v] + (ur[v] - ur[p]) - (dpt[v] - dpt[lca] + 1) * sum[p]
//+ (ru[u] - ru[p]) - (sum[u] - sum[p]) * (dpt[lca] - 1) + dp[u]
//= (ru[u] - ru[p]) - (sum[u] - sum[p]) * (dpt[lca] - 1) + dp[u] - ur[p] + (dpt[lca] - 1) * sum[p]
// + pd[v] + ur[v] + dpt[v] * (-sum[p])
void dsu(int lca, int p, bool keep){
int i, j, mx = -1, bg = -1;
ll c_u_v, c_u_lca_v, c_v_u, c_v_lca_u, q_lca, q_acl;
for(int x : adj[lca]) if(sbtr[x] > mx) mx = sbtr[x], bg = x;
for(int x : adj[lca]) if(x != bg) dsu(x, lca, 0);
if(bg != -1) dsu(bg, lca, 1);
if(x == bg) continue;
q_lca = convex.query(-(ll)dpt[lca] + 1);
q_acl = xevnoc.query(-sum[p]);
for(i = order[x]; i <= order[x] + sbtr[x] - 1; ++i){
int u = vrtx[i];
c_u_v = pd[u] + (ur[u] - ur[p]) - (ll)(dpt[u] - dpt[lca] + 1) * sum[p] - sum[lca] * (ll)(dpt[u] - dpt[lca] + 1) - ru[lca] + sum[lca] * (ll)dpt[lca];
c_u_lca_v =  pd[u] + (ur[u] - ur[p]) - (ll)(dpt[u] - dpt[lca] + 1) * sum[p] - ru[p] + sum[p] * (ll)(dpt[lca] - 1);
c_v_u = (ru[u] - ru[lca]) - (sum[u] - sum[lca]) * (ll)dpt[lca] + dp[u] - ur[p] + (ll)(dpt[lca] - 1) * sum[p] + (sum[u] - sum[lca]) * (ll)(- dpt[lca] + 1);
c_v_lca_u = (ru[u] - ru[p]) - (sum[u] - sum[p]) * (ll)(dpt[lca] - 1) + dp[u] - ur[p] + (ll)(dpt[lca] - 1) * sum[p];
c_u_v += convex.query((ll)dpt[u] - 2 * (ll)dpt[lca] + 1);
c_v_u += xevnoc.query(sum[u] - sum[lca] - sum[p]);
c_u_lca_v += q_lca;
c_v_lca_u += q_acl;
global = max(global, max(c_u_v, c_v_u));
global = max(global, max(c_u_lca_v, c_v_lca_u));
}
for(i = order[x]; i <= order[x] + sbtr[x] - 1; ++i){
int u = vrtx[i];
convex.insert(sum[u], ru[u] + dp[u]);
xevnoc.insert((ll)dpt[u], pd[u] + ur[u]);
}
}
convex.insert(sum[lca], ru[lca] + dp[lca]);
xevnoc.insert((ll)dpt[lca], pd[lca] + ur[lca]);
if(!keep) convex.segments.clear(), xevnoc.segments.clear();
}
void solve(){
int i, j;
dp[n] = pd[n] = sum[n] = ru[n] = ur[n] = 0, dpt[n] = -1;
t = 0, go(0, n, 0);
assert(t == n);
// for0(i, n) val += sbtr[i];
// int mxht = -1;
// for0(i, n) mxht = max(mxht, dpt[i]);
global = -LLONG_MAX;
dsu_prep(0, n, 0);
dsu(0, n, 0);
pl(global), nl;
// pl(global), sp, pl(val), sp, pi(mxht), nl;
}
int main(){
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("0.in", "r", stdin);
// freopen("0.out", "wb", stdout);

// freopen("1.in", "r", stdin);
// freopen("1.out", "wb", stdout);

// freopen("2.in", "r", stdin);
// freopen("2.out", "wb", stdout);

// freopen("3.in", "r", stdin);
// freopen("3.out", "wb", stdout);

// freopen("4.in", "r", stdin);
// freopen("4.out", "wb", stdout);

// freopen("5.in", "r", stdin);
// freopen("5.out", "wb", stdout);

// freopen("6.in", "r", stdin);
// freopen("6.out", "wb", stdout);

// freopen("7.in", "r", stdin);
// freopen("7.out", "wb", stdout);

// freopen("8.in", "r", stdin);
//   freopen("8.out", "wb", stdout);

//  freopen("9.in", "r", stdin);
// freopen("9.out", "wb", stdout);
int cs, ts, total = 0;
si(ts);
assert(ts >= 1 && ts <= 100);
for0(cs, ts){
int i, j;
si(n);
total += n;
assert(n >= 2 && n <= 300000);
for0(i, n){
si(ara[i]);
assert(ara[i] >= -100000 && ara[i] <= 100000);
}
for0(i, n - 1){
int u, v;
sii(u, v);
assert(u >= 1 && u <= n);
assert(v >= 1 && v <= n);
--u, --v;
}
solve();
}
assert(total <= 300000);
}

Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
#define int ll

/*

Copied from rajat1603 (nice usage of comparator).

Dynamic convex Hull

Cool!!!
increasing slopes (lower convex HULL of points(intuitive) , max)
/////////   also change for equality case of slopes **
*/
struct line{
long long a , b;
double xleft;
bool type;
line(long long _a , long long _b){
a = _a;
b = _b;
type = 0;
}
bool operator < (const line &other) const{
if(other.type){
return xleft < other.xleft;
}
return a > other.a;
}
};
double meet(line x , line y){
return 1.0 * (y.b - x.b) / (x.a - y.a);
}
struct cht{
set < line > hull;
cht(){
hull.clear();
}
void resethull(){
hull.clear();
}
typedef set < line > :: iterator ite;
bool hasleft(ite node){
return node != hull.begin();
}
bool hasright(ite node){
return node != prev(hull.end());
}
void updateborder(ite node){
if(hasright(node)){
line temp = *next(node);
hull.erase(temp);
temp.xleft = meet(*node , temp);
hull.insert(temp);
}
if(hasleft(node)){
line temp = *node;
temp.xleft = meet(*prev(node) , temp);
hull.erase(node);
hull.insert(temp);
}
else{
line temp = *node;
hull.erase(node);
temp.xleft = -1e18;
hull.insert(temp);
}
}
bool useless(line left , line middle , line right){
return meet(left , middle) > meet(middle , right);
}
bool useless(ite node){
if(hasleft(node) && hasright(node)){
return useless(*prev(node) , *node , *next(node));
}
return 0;
}
void addline(long long a , long long b){
a*=-1;
b*=-1;
line temp = line(a , b);
auto it = hull.lower_bound(temp);
if(it != hull.end() && it -> a == a){
if(it -> b > b){
hull.erase(it);
}
else{
return;
}
}
hull.insert(temp);
it = hull.find(temp);
if(useless(it)){
hull.erase(it);
return;
}
while(hasleft(it) && useless(prev(it))){
hull.erase(prev(it));
}
while(hasright(it) && useless(next(it))){
hull.erase(next(it));
}
updateborder(it);
}
long long getbest(long long x){
if(hull.empty()){
return -1e18;
}
line query(0 , 0);
query.xleft = x;
query.type = 1;
auto it = hull.lower_bound(query);
it = prev(it);
return -1*(it -> a * x + it -> b);
}
};

cht hull1;
cht hull2;

int resethull(){
hull1.resethull();
hull2.resethull();
offseta1 = 0;
offseta2 = 0;
offsetb1 = 0;
offsetb2 = 0;
return 0;
}

void insertline1(int a,int b){
}

void insertline2(int a,int b){
}

int foo[312345];
int moveup(int cur){
offseta2++;

offseta1+=foo[cur];
return 0;
}

int query2(int x){
val+=offsetb2;
//max2=max(max2,val);
return val;
}

int query1(int x){
val+=offsetb1;
//max1=max(max1,val);
return val;
}

int par[312345],subtree[312345];
int dep[312345];
int sum1[312345],sum2[312345],sumn[312345];
int dfs1(int cur,int paren){
dep[cur]=dep[paren]+1;
par[cur]=paren;
sumn[cur]=sumn[paren]+foo[cur];
sum2[cur]=sum2[paren]+sumn[cur];
sum1[cur]=dep[cur]*foo[cur]+sum1[paren];
subtree[cur]=1;
int i;
}
}
return 0;
}

int dp1[312345],dp2[312345];

int maxi;
int dfs2(int cur,int ances){
int i;
int val=query1(dep[cur]-dep[ances]+1)+dp2[cur];
val+=sum2[cur]-sum2[ances];
val-=sumn[ances]*(dep[cur]-dep[ances]);
maxi=max(maxi,val);
val=query2(sumn[cur]-sumn[ances])+dp1[cur];
val+=sum1[cur]-sum1[ances];
val-=(dep[ances])*(sumn[cur]-sumn[ances]);
maxi=max(maxi,val);
continue;
}
return 0;
}

int i;
int val=sum1[cur]-sum1[ances] - (dep[ances]+1)*(sumn[cur]-sumn[ances]);
insertline1(sumn[cur]-sumn[ances],dp1[cur]+val);

val=sum2[cur]-sum2[ances]-(dep[cur]-dep[ances])*sumn[ances];
insertline2(dep[cur]-dep[ances],dp2[cur]+val);
continue;
}
return 0;
}
// dp1 starts after i and goes down
// dp2 ends after i and goes up from down.
int dfs(int cur){
int i;
int maxim=0,child=-1;
}
}
}
resethull();
}
}
if(child==-1){
dp1[cur]=0;
dp2[cur]=0;
insertline1(0,dp1[cur]);
insertline2(0,dp2[cur]);
moveup(cur);
return 0;
}
dfs(child);
}
}
dp1[cur]=query1(2)+foo[cur];
dp2[cur]=query2(foo[cur])+foo[cur];
maxi=max(maxi,dp1[cur]);
maxi=max(maxi,dp2[cur]);
dp1[cur]=max(dp1[cur],0LL);
dp2[cur]=max(dp2[cur],0LL);
insertline1(0,dp1[cur]);
insertline2(0,dp2[cur]);
moveup(cur);
return 0;
}
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
maxi=inf;
maxi*=inf;
maxi*=-1;
int n;
cin>>n;
resethull();
int i;
f(i,1,n+1){
cin>>foo[i];
}
int u,v;
rep(i,n-1){
cin>>u>>v;
}
dfs1(1,0);
dfs(1);
cout<<maxi<<endl;
}
}


UPDATE: Added Setter and tester solutions too
UPDATE: Slight mistake in above explanation. I really apologize for inconvenience.

1 Like

The first 6 editorials are posted.

1 Like