Texte vergleichen

Finde den Unterschied zwischen zwei Textdateien

Live-Editor

Gleiches ausblenden

Zeilenumbruch aus

Ansicht

Vergleichsgenauigkeit

Syntaxhervorhebung

Diffchecker Desktop Der sicherste Weg, Diffchecker zu nutzen. Hol dir die Desktop-App: Deine Diffs verlassen nie deinen Computer!Desktop holen

temp

Erstellt vor 6 JahrenDiff läuft nie ab

14 Entfernungen

Zeilen
Gesamt
Entfernt

Zeichen
Gesamt
Entfernt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

272 Zeilen

26 Hinzufügungen

Zeilen
Gesamt
Hinzugefügt

Zeichen
Gesamt
Hinzugefügt

Um diese Funktion weiterhin zu nutzen, aktualisiere auf Diffchecker Pro Preise anzeigen

280 Zeilen

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

}

Gespeicherte Diffs

Originaltext

Datei öffnen

#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;
}

Bearbeitung

Datei öffnen

#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;
}