QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#667249#9492. 树上简单求和Galex0 4470ms88376kbC++235.8kb2024-10-22 21:51:232024-10-22 21:51:34

Judging History

This is the latest submission verdict.

  • [2024-10-22 21:51:34]
  • Judged
  • Verdict: 0
  • Time: 4470ms
  • Memory: 88376kb
  • [2024-10-22 21:51:23]
  • Submitted

answer

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pii pair<int, int>
#define pll pair<LL, LL>
#define fi first
#define se second
#define mkp make_pair
#define sz(x) (int)x.size()
using namespace std;
bool Mst;

LL read() {
	LL s = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		f = (ch == '-' ? -1 : 1), ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}

ULL readull() {
	ULL s = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s;
}

mt19937 rnd(1919810);

const int MAXN = 200005;

int n, m;
ULL a[MAXN];
vector<int> e[MAXN];
int fa[MAXN][20], dep[MAXN], Fa[MAXN];
int dfn[MAXN], tim = 0, rnk[MAXN];

void pre(int x, int fat) {
	fa[x][0] = Fa[x] = fat, dep[x] = dep[fat] + 1;
	dfn[x] = ++tim, rnk[tim] = x;
	for (int y : e[x])
		if (y != fat)
			pre(y, x);
}

int mov(int u, int d) {
	for (int i = 18; i >= 0; i--)
		if ((1 << i) <= d)
			d -= (1 << i), u = fa[u][i];
	return u;
}

int lca(int u, int v) {
	dep[u] > dep[v] ? u = mov(u, dep[u] - dep[v]) : v = mov(v, dep[v] - dep[u]);
	if (u == v) return u;
	for (int i = 18; i >= 0; i--)
		if (fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

namespace Blocker {
	const int MAXC = 505;
	int B, C;
	int L[MAXC], R[MAXC], bl[MAXN];
	ULL sum[MAXC], val[MAXN];
	void init() {
		B = sqrt(n), C = (n - 1) / B + 1;
		for (int i = 1; i <= n; i++)
			bl[i] = (i - 1) / B + 1, R[bl[i]] = i;
		for (int i = n; i; i--)
			L[bl[i]] = i;
	}
	void mdf(int x, ULL v) {
		for (int i = x; i <= R[bl[x]]; i++) val[i] += v;
		for (int i = bl[x]; i <= C; i++) sum[i] += v;
	}
	inline ULL qry(int x) { return val[x] + sum[bl[x] - 1];}
	inline ULL qry(int l, int r) {
		return qry(r) - qry(l - 1);
	}
}

namespace Tree1 {
	vector<int> e[MAXN];
	void add(int u, int v) {
		e[u].push_back(v);
		e[v].push_back(u);
	}
	int fa[MAXN][20], dep[MAXN], dfn[MAXN], rnk[MAXN], tim = 0, sz[MAXN], o[MAXN], Fa[MAXN], id[MAXN];
	void pre(int x, int fat) {
		dfn[x] = ++tim, rnk[tim] = x, sz[x] = 1;
		fa[x][0] = Fa[x] = fat, dep[x] = dep[fat] + 1;
		for (int y : e[x])
			if (y != fat)
				pre(y, x), sz[x] += sz[y];
	}
	int mov(int u, int d) {
		for (int i = 18; i >= 0; i--)
			if ((1 << i) <= d)
				d -= (1 << i), u = fa[u][i];
		return u;
	}
	int lca(int u, int v) {
		dep[u] > dep[v] ? u = mov(u, dep[u] - dep[v]) : v = mov(v, dep[v] - dep[u]);
		if (u == v) return u;
		for (int i = 18; i >= 0; i--)
			if (fa[u][i] != fa[v][i])
				u = fa[u][i], v = fa[v][i];
		return fa[u][0];
	}
	void pre() {
		pre(1, 0);
		for (int j = 1; j <= 18; j++)
			for (int i = 1; i <= n; i++)
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
		for (int i = 1; i <= n; i++) o[i] = i;
		sort(o + 1, o + n + 1, [](int x, int y) {return dep[x] < dep[y];});
	}
	void mdf(int x, int y, int l, ULL k) {
		Blocker::mdf(dfn[x], k), Blocker::mdf(dfn[y], k);
		Blocker::mdf(dfn[l], -k), Blocker::mdf(dfn[Fa[l]], -k);
	}
	inline ULL qry(int x) {
		return Blocker::qry(dfn[x], dfn[x] + sz[x] - 1) + a[x];
	}
	int sum[MAXN];
	void intot(int lst) {
		lst = id[lst];
		for (int i = lst; i > 1; i--) {
			int x = o[i];
			sum[Fa[x]] += sum[x];
		}
		for (int i = 2; i <= n; i++) {
			int x = o[i];
			sum[x] += sum[Fa[x]];
		}
	}
	int qry(int u, int v, int l) {
		return sum[u] + sum[v] - sum[l] - sum[Fa[l]];
	}
}

int p[MAXN], cnt = 0;
bitset<MAXN> in;

void spread() {
	cnt = 2000;
	for (int i = 1; i <= cnt; i++) p[i] = rnd() % n + 1;
	p[++cnt] = 1;
	sort(p + 1, p + cnt + 1, [](int x, int y) {return dfn[x] < dfn[y];});
	for (int i = 2, len = cnt; i <= len; i++) p[++cnt] = lca(p[i], p[i - 1]);
	sort(p + 1, p + cnt + 1, [](int x, int y) {return dfn[x] < dfn[y];});
	cnt = unique(p + 1, p + cnt + 1) - p - 1;
	int mx = 0;
	for (int i = 2; i <= cnt; i++) mx = max(mx, dep[p[i]] - dep[p[i - 1]]);
	cerr << mx << endl;
	for (int i = 1; i <= cnt; i++) in[p[i]] = 1;
}

int x[MAXN], y[MAXN], l1[MAXN];
int p1[MAXN], p2[MAXN], p3[MAXN];
ULL ans[MAXN], k[MAXN];
int MAX = 0, CNT = 0;

int qry(int u, int i, ULL v) {
	while (!in[u])
		ans[i] += v * Tree1::qry(u), u = Fa[u], CNT++;
	return u;
}

bool Med;
signed main() {
	// freopen("mist5-1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	fprintf(stderr, "%.2lfMB\n", abs(&Med - &Mst) / 1048576.0);
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = readull();
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		Tree1::add(u, v);
	}
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		e[u].push_back(v), e[v].push_back(u);
	}
	pre(1, 0), Tree1::pre();
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	Blocker::init(), spread();
	cerr << cnt << endl;
	for (int i = 1; i <= m; i++) {
		x[i] = read(), y[i] = read(), k[i] = readull(), l1[i] = Tree1::lca(x[i], y[i]);
		Tree1::mdf(x[i], y[i], l1[i], k[i]);
		p1[i] = qry(x[i], i, 1), p2[i] = qry(y[i], i, 1);
		int l = lca(x[i], y[i]);
		p3[i] = qry(l, i, -2), ans[i] += Tree1::qry(l);
	}
	cerr << CNT << endl;
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	for (int i = 1; i <= cnt; i++) {
		memset(Tree1::sum, 0, sizeof Tree1::sum);
		ULL res = 0;
		Tree1::sum[p[i]]++;
		Tree1::intot(p[i]);
		for (int j = 1; j <= m; j++) {
			int c = Tree1::qry(x[j], y[j], l1[j]);
			// cout << c << endl;
			res += k[j] * c;
			if (p1[j] == p[i]) ans[j] += res;
			if (p2[j] == p[i]) ans[j] += res;
			if (p3[j] == p[i]) ans[j] -= res * 2;
		}
	}
	for (int i = 1; i <= m; i++)
		printf("%llu\n", ans[i]);
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 38ms
memory: 25032kb

input:

3000 3000
7236742292501328495 17973811477309806363 16075782662531676171 17971236571771878676 11392080645527132110 3685563455925680459 9773593720088356683 8313828403245053795 7736401634567449043 1634817828009987181 6951124933529719486 12775126714635387213 15460977209223753216 397573676785925632 31372...

output:

13297593570177758630
11691129906858450481
12523963591364995742
14771575308982008238
4020473979240330311
11311490384750113474
3866286450224650517
13836189064527762322
7242781245929975772
11946669602301276325
9879254669618897391
6618542724020675023
13104283394558819753
16836448482968225970
64497706235...

result:

wrong answer 1st lines differ - expected: '12105153858659381124', found: '13297593570177758630'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 3278ms
memory: 78844kb

input:

200000 200000
622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...

output:

1147709447001994397
3574539290845775799
4043350647474894001
11860189752154651707
5098454253452223725
14010453301459161270
2010482116821664867
6699587514927494110
11295115813945599076
6192915283879028746
13749927555471408202
15569598095798951340
14482745111969254025
15121443654167386950
1742701384205...

result:

wrong answer 1st lines differ - expected: '9042998055336671259', found: '1147709447001994397'

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 4470ms
memory: 87716kb

input:

200000 200000
1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...

output:

9834355145273575495
11390026854978177919
2915647538116222701
15077357159030174118
17087912101331349855
13571497522883167649
1724207551452208483
1918175960780791199
7363608009800000325
7859087167427875074
15164572888351903324
14092900006352745642
17118376817093575411
11973439704832781523
162929443954...

result:

wrong answer 1st lines differ - expected: '11479812171669345085', found: '9834355145273575495'

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 2570ms
memory: 88376kb

input:

200000 200000
6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...

output:

14542094257572878011
11659833584518562958
4194728657136713678
16149641950669417494
14688776788685804470
7261736560374764423
1429611116586707191
5077189944062473684
13102975918461702139
17193497963995604189
14940338950670328047
10213701590817442116
5745866376775355171
1250739604043792565
157798173112...

result:

wrong answer 1st lines differ - expected: '5519324519442957729', found: '14542094257572878011'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%