temp
18 removals
272 lines
27 additions
280 lines
#include "bits/stdc++.h"
#include "bits/stdc++.h"
using namespace std;
using namespace std;
#ifndef LOCAL
#ifndef LOCAL
#define endl '\n'
#define endl '\n'
#endif
#endif
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pf push_front
#define pb push_back
#define pb push_back
#define fi first
#define fi first
#define se second
#define se second
#define all(x) x.begin(), x.end()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define sz(x) (int)x.size()
#define rsz resize()
#define rsz resize()
#define lb lower_bound
#define lb lower_bound
#define ub upper_bound
#define ub upper_bound
#define br cout << endl
#define br cout << endl
typedef long long ll;
typedef long long ll;
typedef long double f80;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,ll> pll;
int pct(int x) { return __builtin_popcount(x); }
int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int bit(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bit(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bit(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int bit(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
template<typename T>
template<typename T>
void leftShift(vector<T> &v, ll k) { k %= sz(v); if(k < 0) k += sz(v); rotate(v.begin(), v.begin() + k, v.end()); }
void leftShift(vector<T> &v, ll k) { k %= sz(v); if(k < 0) k += sz(v); rotate(v.begin(), v.begin() + k, v.end()); }
template<typename T>
template<typename T>
void rightSift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }
void rightSift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
ll rand(ll l, ll r){
uniform_int_distribution<ll> uid(l, r);
uniform_int_distribution<ll> uid(l, r);
return uid(rng);
return uid(rng);
}
}
inline int nxt() {
inline int nxt() {
int x;
int x;
cin >> x;
cin >> x;
return x;
return x;
}
}
inline ll nxtll() {
inline ll nxtll() {
ll x;
ll x;
cin >> x;
cin >> x;
return x;
return x;
}
}
void pr() {}
void pr() {}
void sc() {}
void sc() {}
template <typename Head, typename... Tail>
template <typename Head, typename... Tail>
void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }
void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }
template <typename Head, typename... Tail>
template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }
#ifdef LOCAL
#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#else
#define debug(...) 42
#define debug(...) 42
#endif
#endif
#ifndef LOCAL
#ifndef LOCAL
string to_string(__int128 x) {
string to_string(__int128 x) {
string s = "";
string s = "";
bool neg = 0;
bool neg = 0;
if(x < 0) { s += "-"; neg = 1; x = -x; }
if(x < 0) { s += "-"; neg = 1; x = -x; }
if(!x) s += '0';
if(!x) s += '0';
while(x) {
while(x) {
int rem = x % 10;
int rem = x % 10;
s += to_string(rem);
s += to_string(rem);
x /= 10;
x /= 10;
}
}
reverse(s.begin() + neg, s.end());
reverse(s.begin() + neg, s.end());
return s;
return s;
}
}
#endif
#endif
const int mod = 1e9 + 7; // 998244353;
const int mod = 1e9 + 7; // 998244353;
int pwr(int a,int b) {
int pwr(int a,int b) {
int ans = 1;
int ans = 1;
while(b) {
while(b) {
if(b & 1) ans = (ans * 1LL * a) % mod;
if(b & 1) ans = (ans * 1LL * a) % mod;
a = (a * 1LL * a) % mod;
a = (a * 1LL * a) % mod;
b >>= 1;
b >>= 1;
}
}
return ans;
return ans;
}
}
/*
/*
Lookout for overflows!!
Lookout for overflows!!
Check array sizes!!
Check array sizes!!
Clear before test cases!!
Clear before test cases!!
Use the correct modulo!!
Use the correct modulo!!
Check for corner cases!!
Check for corner cases!!
Are you forgetting something?!
Are you forgetting something?!
Read problem statement carefully!!!
Read problem statement carefully!!!
*/
*/
/**
/**
* Author: Simon Lindholm
* Author: Simon Lindholm
* Date: 2017-04-20
* Date: 2017-04-20
* License: CC0
* License: CC0
* Source: own work
* Source: own work
* Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
* Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
* Useful for dynamic programming (``convex hull trick'').
* Useful for dynamic programming (``convex hull trick'').
* Time: O(\log N)
* Time: O(\log N)
* Status: stress-tested
* Status: stress-tested
*/
*/
struct Line {
struct Line {
mutable ll k, m, p;
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
bool operator<(ll x) const { return p < x; }
};
};
struct LineContainer : multiset<Line, less<>> {
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (y == end()) { x->p = inf; return false; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
return x->p >= y->p;
}
}
void add(ll k, ll m) {
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
isect(x, erase(y));
}
}
ll query(ll x) {
ll query(ll x) {
if(empty()) return -1e18;
if(empty()) return -1e18;
auto l = *lower_bound(x);
auto l = *lower_bound(x);
return l.k * x + l.m;
return l.k * x + l.m;
}
}
};
};
const int N = 2e5 + 5;
const int N = 3e5 + 5;
ll a[N], depth[N], sz[N], s[N], p[N], r[N];
ll a[N], depth[N], sz[N], s[N], p[N], r[N], dp[N], dp1[N];
ll ans = -1e18;
vector<int> g[N];
vector<int> g[N];
LineContainer ch[N], ch1[N];
LineContainer ch[N], ch1[N];
int lol[N];
int lol[N];
void pre_dfs(int u,int pp) {
void pre_dfs(int u,int pp) {
depth[u] = depth[pp] + 1;
depth[u] = depth[pp] + 1;
sz[u] = 1;
sz[u] = 1;
s[u] = s[pp] + a[u];
s[u] = s[pp] + a[u];
r[u] = r[pp] + s[u];
r[u] = r[pp] + s[u];
p[u] = p[pp] + depth[u] * 1LL * a[u];
p[u] = p[pp] + depth[u] * 1LL * a[u];
for(int v : g[u]) {
for(int v : g[u]) {
if(v != pp) {
if(v != pp) {
pre_dfs(v, u);
pre_dfs(v, u);
sz[u] += sz[v];
sz[u] += sz[v];
}
}
}
}
}
}
ll ans = 0;
void _add(int ss,int u) {
void _add(int ss,int u) {
ch[ss].add(s[u], p[u]);
ch[ss].add(s[u], p[u] + dp[u]);
}
}
ll _query(int ss, int u2, int u) {
ll _query(int ss, int u2, int u) {
int l2 = depth[u2] - depth[u] - 1;
int l2 = depth[u2] - depth[u] - 1;
ll x = l2 + 2 - depth[u];
ll x = l2 + 2 - depth[u];
ll c = -p[u] + depth[u] * s[u] - (l2 + 2) * s[u] + a[u] * (l2 + 2) + (r[u2] - r[u]) - (l2 + 1) * s[u];
ll c = dp1[u2] - p[u] + depth[u] * s[u] - (l2 + 2) * s[u] + a[u] * (l2 + 2) + (r[u2] - r[u]) - (l2 + 1) * s[u];
return ch[ss].query(x) + c;
return ch[ss].query(x) + c;
}
}
void _add1(int ss,int u) {
void _add1(int ss,int u) {
ch1[ss].add(depth[u], r[u]);
ch1[ss].add(depth[u], r[u] + dp1[u]);
}
}
ll _query1(int ss, int u2, int u) {
ll _query1(int ss, int u2, int u) {
int l2 = depth[u2] - depth[u] - 1;
int l2 = depth[u2] - depth[u] - 1;
ll x = -2 * s[u] + a[u] + s[u2];
ll x = -2 * s[u] + a[u] + s[u2];
ll c = p[u2] - p[u] + 2 * depth[u] * s[u] - depth[u] * s[u2] + (-depth[u] + 1) * (s[u2] - s[u]) - r[u] - depth[u] * a[u] + a[u];
ll c = dp[u2] + p[u2] - p[u] + 2 * depth[u] * s[u] - depth[u] * s[u2] + (-depth[u] + 1) * (s[u2] - s[u]) - r[u] - depth[u] * a[u] + a[u];
return ch1[ss].query(x) + c;
return ch1[ss].query(x) + c;
}
}
void dfs2(int u2, int p, int u, bool add) {
void dfs2(int u2, int p, int u, bool add) {
if(!add) {
if(!add) {
ans = max(ans, _query(lol[u], u2, u));
ans = max(ans, _query(lol[u], u2, u));
ans = max(ans, _query1(lol[u], u2, u));
ans = max(ans, _query1(lol[u], u2, u));
}
}
else {
else {
_add(lol[u], u2);
_add(lol[u], u2);
_add1(lol[u], u2);
_add1(lol[u], u2);
}
}
for(int v : g[u2]) {
for(int v : g[u2]) {
if(v != p) {
if(v != p) {
dfs2(v, u2, u, add);
dfs2(v, u2, u, add);
}
}
}
}
}
}
void dfs(int u,int p) {
void dfs(int u,int p) {
int hc = -1, S = -1;
int hc = -1, S = -1;
for(int v : g[u]) {
for(int v : g[u]) {
if(v != p) {
if(v != p) {
dfs(v, u);
dfs(v, u);
if(sz[v] > S) {
if(sz[v] > S) {
S = sz[v], hc = v;
S = sz[v], hc = v;
}
}
}
}
}
}
if(hc == -1) {
if(hc == -1) {
lol[u] = u;
lol[u] = u;
}
}
else {
else {
lol[u] = lol[hc];
lol[u] = lol[hc];
}
}
Text moved with changes to lines 236-241 (90.4% similarity)
ll q = _query(lol[u], u, u);
ll q1 = _query1(lol[u], u, u);
ans = max(ans, q);
ans = max(ans, q1);
_add(lol[u], u);
_add1(lol[u], u);
for(int v : g[u]) {
for(int v : g[u]) {
if(v != p && v != hc) {
if(v != p && v != hc) {
dfs2(v, u, u, 0);
dfs2(v, u, u, 0);
dfs2(v, u, u, 1);
dfs2(v, u, u, 1);
}
}
}
}
ll q = _query(lol[u], u, u);
ll q1 = _query1(lol[u], u, u);
Text moved with changes from lines 228-233 (90.4% similarity)
dp[u] = max(q, 0LL);
dp1[u] = max(q1, 0LL);
ans = max(ans, q);
ans = max(ans, q1);
_add(lol[u], u);
_add1(lol[u], u);
}
}
void solve() {
void solve() {
ans = -1e18;
int n;
int n;
sc(n);
sc(n);
fr(i, 1, n) {
ch[i].clear();
ch1[i].clear();
dp[i] = dp1[i] = 0;
r[i] = p[i] = s[i] = 0;
g[i].clear();
sc(a[i]);
}
fr(i, 1, n - 1) {
fr(i, 1, n - 1) {
int u, v;
int u, v;
sc(u, v);
sc(u, v);
g[u].pb(v);
g[u].pb(v);
g[v].pb(u);
g[v].pb(u);
}
}
fr(i, 1, n) {
sc(a[i]);
ans = max(ans, (ll)a[i]);
}
int r = 1;
int r = 1;
pre_dfs(r, 0);
pre_dfs(r, 0);
dfs(r, 0);
dfs(r, 0);
pr(ans);
pr(ans);
br;
}
}
signed main() {
signed main() {
ios :: sync_with_stdio(0);
ios :: sync_with_stdio(0);
cin.tie(0);
cin.tie(0);
cout.tie(0);
cout.tie(0);
int t;
int t;
// cin >> t;
cin >> t;
t = 1;
// t = 1;
for(int tt = 1; tt <= t; tt++) {
for(int tt = 1; tt <= t; tt++) {
solve();
solve();
}
}
return 0;
return 0;
}
}