Confronta il testo

Trova la differenza tra due file di testo

Editor live

Comprimi invariate

Senza a capo

Layout

Livello di dettaglio

Evidenziazione sintassi

Diffchecker Desktop Il modo più sicuro per usare Diffchecker. Ottieni l'app Diffchecker Desktop: i tuoi diff non lasciano mai il tuo computer!Ottieni Desktop

temp

Creato 6 anni faIl diff non scade mai

14 rimozioni

Linee
Totale
Rimosso

Caratteri
Totale
Rimosso

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

272 linee

26 aggiunte

Linee
Totale
Aggiunto

Caratteri
Totale
Aggiunto

Per continuare a utilizzare questa funzione, aggiorna a Diffchecker Pro Visualizza prezzi

280 linee

#include "bits/stdc++.h"

using namespace std;

#ifndef LOCAL

#define endl '\n'

#endif

#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 pf push_front

#define pb push_back

#define fi first

#define se second

#define all(x) x.begin(), x.end()

#define rall(x) x.rbegin(), x.rend()

#define sz(x) (int)x.size()

#define rsz resize()

#define lb lower_bound

#define ub upper_bound

#define br cout << endl

typedef long long ll;

typedef long double f80;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }

int pct(ll x) { return __builtin_popcountll(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 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); }

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()); }

template<typename T>

void rightSift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){

uniform_int_distribution<ll> uid(l, r);

return uid(rng);

}

inline int nxt() {

int x;

cin >> x;

return x;

}

inline ll nxtll() {

ll x;

cin >> x;

return x;

}

void pr() {}

void sc() {}

template <typename Head, typename... Tail>

void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }

template <typename Head, typename... Tail>

void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL

#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

#else

#define debug(...) 42

#endif

#ifndef LOCAL

string to_string(__int128 x) {

string s = "";

bool neg = 0;

if(x < 0) { s += "-"; neg = 1; x = -x; }

if(!x) s += '0';

while(x) {

int rem = x % 10;

s += to_string(rem);

x /= 10;

}

reverse(s.begin() + neg, s.end());

return s;

}

#endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,int b) {

int ans = 1;

while(b) {

if(b & 1) ans = (ans * 1LL * a) % mod;

a = (a * 1LL * a) % mod;

b >>= 1;

}

return ans;

}

Lookout for overflows!!

Check array sizes!!

Clear before test cases!!

Use the correct modulo!!

Check for corner cases!!

Are you forgetting something?!

Read problem statement carefully!!!

/**

* Author: Simon Lindholm

* Date: 2017-04-20

* License: CC0

* Source: own work

* 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'').

* Time: O(\log N)

* Status: stress-tested

struct Line {

mutable ll k, m, p;

bool operator<(const Line& o) const { return k < o.k; }

bool operator<(ll x) const { return p < x; }

};

struct LineContainer : multiset<Line, less<>> {

// (for doubles, use inf = 1/.0, div(a,b) = a/b)

const ll inf = LLONG_MAX;

ll div(ll a, ll b) { // floored division

return a / b - ((a ^ b) < 0 && a % b); }

bool isect(iterator x, iterator y) {

if (y == end()) { x->p = inf; return false; }

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);

return x->p >= y->p;

}

void add(ll k, ll m) {

auto z = insert({k, m, 0}), y = z++, x = y;

while (isect(y, z)) z = erase(z);

if (x != begin() && isect(--x, y)) isect(x, y = erase(y));

while ((y = x) != begin() && (--x)->p >= y->p)

isect(x, erase(y));

}

ll query(ll x) {

if(empty()) return -1e18;

auto l = *lower_bound(x);

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];

LineContainer ch[N], ch1[N];

int lol[N];

void pre_dfs(int u,int pp) {

depth[u] = depth[pp] + 1;

sz[u] = 1;

s[u] = s[pp] + a[u];

r[u] = r[pp] + s[u];

p[u] = p[pp] + depth[u] * 1LL * a[u];

for(int v : g[u]) {

if(v != pp) {

pre_dfs(v, u);

sz[u] += sz[v];

}

ll ans = 0;

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) {

int l2 = depth[u2] - depth[u] - 1;

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;

}

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) {

int l2 = depth[u2] - depth[u] - 1;

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;

}

void dfs2(int u2, int p, int u, bool add) {

if(!add) {

ans = max(ans, _query(lol[u], u2, u));

ans = max(ans, _query1(lol[u], u2, u));

}

else {

_add(lol[u], u2);

_add1(lol[u], u2);

}

for(int v : g[u2]) {

if(v != p) {

dfs2(v, u2, u, add);

}

void dfs(int u,int p) {

int hc = -1, S = -1;

for(int v : g[u]) {

if(v != p) {

dfs(v, u);

if(sz[v] > S) {

S = sz[v], hc = v;

}

if(hc == -1) {

lol[u] = u;

}

else {

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]) {

if(v != p && v != hc) {

dfs2(v, u, u, 0);

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() {

ans = -1e18;

int 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) {

int u, v;

sc(u, v);

g[u].pb(v);

g[v].pb(u);

}

fr(i, 1, n) {

sc(a[i]);

ans = max(ans, (ll)a[i]);

}

int r = 1;

pre_dfs(r, 0);

dfs(r, 0);

pr(ans);

br;

}

signed main() {

ios :: sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t;

// cin >> t;

cin >> t;

t = 1;

// t = 1;

for(int tt = 1; tt <= t; tt++) {

solve();

}

return 0;

}

Diff salvati

Testo originale

Apri file

#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#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 pf push_front
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define rsz resize()
#define lb lower_bound
#define ub upper_bound
#define br cout << endl

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(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 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); }

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()); }
template<typename T>
void rightSift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

inline ll nxtll() {
	ll x;
	cin >> x;
	return x;
}

void pr() {}
void sc() {}

template <typename Head, typename... Tail>
void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#ifndef LOCAL
string to_string(__int128 x) {
	string s = "";
	bool neg = 0;
	if(x < 0) { s += "-"; neg = 1; x = -x; }
	if(!x) s += '0';
	while(x) {
		int rem = x % 10;
		s += to_string(rem);
		x /= 10;
	}
	reverse(s.begin() + neg, s.end());
	return s;
}
#endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

/**
 * Author: Simon Lindholm
 * Date: 2017-04-20
 * License: CC0
 * Source: own work
 * 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'').
 * Time: O(\log N)
 * Status: stress-tested
 */

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		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);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		if(empty()) return -1e18;
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

const int N = 2e5 + 5;
ll a[N], depth[N], sz[N], s[N], p[N], r[N];
vector<int> g[N];

LineContainer ch[N], ch1[N];
int lol[N];

void pre_dfs(int u,int pp) {
	depth[u] = depth[pp] + 1;
	sz[u] = 1;
	s[u] = s[pp] + a[u];
	r[u] = r[pp] + s[u];
	p[u] = p[pp] + depth[u] * 1LL * a[u];
	for(int v : g[u]) {
		if(v != pp) {
			pre_dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

ll ans = 0;
void _add(int ss,int u) {
	ch[ss].add(s[u], p[u]);
}

ll _query(int ss, int u2, int u) {
	int l2 = depth[u2] - depth[u] - 1;
	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];
	return ch[ss].query(x) + c;
}

void _add1(int ss,int u) {
	ch1[ss].add(depth[u], r[u]);
}

ll _query1(int ss, int u2, int u) {
	int l2 = depth[u2] - depth[u] - 1;
	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];
	return ch1[ss].query(x) + c;
}

void dfs2(int u2, int p, int u, bool add) {
	if(!add) {
		ans = max(ans, _query(lol[u], u2, u));
		ans = max(ans, _query1(lol[u], u2, u));
	}
	else {
		_add(lol[u], u2);
		_add1(lol[u], u2);
	}
	for(int v : g[u2]) {
		if(v != p) {
			dfs2(v, u2, u, add);
		}
	}
}

void dfs(int u,int p) {
	int hc = -1, S = -1;
	for(int v : g[u]) {
		if(v != p) {
			dfs(v, u);
			if(sz[v] > S) {
				S = sz[v], hc = v;
			}
		}
	}
	if(hc == -1) {
		lol[u] = u;
	}
	else {
		lol[u] = lol[hc];
	}
	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]) {
		if(v != p && v != hc) {
			dfs2(v, u, u, 0);
			dfs2(v, u, u, 1);
		}
	}
}

void solve() {
	int n;
	sc(n);
	fr(i, 1, n - 1) {
		int u, v;
		sc(u, v);
		g[u].pb(v);
		g[v].pb(u);
	}
	fr(i, 1, n) {
		sc(a[i]);
		ans = max(ans, (ll)a[i]);
	}
	int r = 1;
	pre_dfs(r, 0);
	dfs(r, 0);
	pr(ans);
}

signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	// cin >> t;
	t = 1;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

Testo modificato

Apri file

#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

inline ll nxtll() {
	ll x;
	cin >> x;
	return x;
}

void pr() {}
void sc() {}

template <typename Head, typename... Tail>
void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

const int N = 3e5 + 5;
ll a[N], depth[N], sz[N], s[N], p[N], r[N], dp[N], dp1[N];
ll ans = -1e18;
vector<int> g[N];

LineContainer ch[N], ch1[N];
int lol[N];

void _add(int ss,int u) {
	ch[ss].add(s[u], p[u] + dp[u]);
}

ll _query(int ss, int u2, int u) {
	int l2 = depth[u2] - depth[u] - 1;
	ll x = l2 + 2 - depth[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;
}

void _add1(int ss,int u) {
	ch1[ss].add(depth[u], r[u] + dp1[u]);
}

ll _query1(int ss, int u2, int u) {
	int l2 = depth[u2] - depth[u] - 1;
	ll x = -2 * s[u] + a[u] + s[u2];
	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;
}

void dfs(int u,int p) {
	int hc = -1, S = -1;
	for(int v : g[u]) {
		if(v != p) {
			dfs(v, u);
			if(sz[v] > S) {
				S = sz[v], hc = v;
			}
		}
	}
	if(hc == -1) {
		lol[u] = u;
	}
	else {
		lol[u] = lol[hc];
	}
	for(int v : g[u]) {
		if(v != p && v != hc) {
			dfs2(v, u, u, 0);
			dfs2(v, u, u, 1);
		}
	}
	ll q = _query(lol[u], u, u);
	ll q1 = _query1(lol[u], u, u);
	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() {
	ans = -1e18;
	int 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) {
		int u, v;
		sc(u, v);
		g[u].pb(v);
		g[v].pb(u);
	}
	int r = 1;
	pre_dfs(r, 0);
	dfs(r, 0);
	pr(ans);
	br;
}

signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	// t = 1;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}