QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#666855#9492. 树上简单求和zlt0 5112ms90444kbC++143.9kb2024-10-22 20:13:432024-10-22 20:13:43

Judging History

你现在查看的是最新测评结果

  • [2024-10-22 20:13:43]
  • 评测
  • 测评结果:0
  • 用时:5112ms
  • 内存:90444kb
  • [2024-10-22 20:13:43]
  • 提交

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 200100;

int n, m;
ull a[maxn], c[maxn];

struct Tree {
	vector<int> G[maxn];
	
	inline void add_edge(int u, int v) {
		G[u].pb(v);
		G[v].pb(u);
	}
	
	int fa[maxn], sz[maxn], son[maxn], dep[maxn], top[maxn], dfn[maxn], rnk[maxn], tim;
	
	int dfs(int u, int f, int d) {
		fa[u] = f;
		sz[u] = 1;
		dep[u] = d;
		int mx = -1;
		for (int v : G[u]) {
			if (v == f) {
				continue;
			}
			sz[u] += dfs(v, u, d + 1);
			if (sz[v] > mx) {
				son[u] = v;
				mx = sz[v];
			}
		}
		return sz[u];
	}
	
	void dfs2(int u, int tp) {
		top[u] = tp;
		dfn[u] = ++tim;
		rnk[tim] = u;
		if (!son[u]) {
			return;
		}
		dfs2(son[u], tp);
		for (int v : G[u]) {
			if (!dfn[v]) {
				dfs2(v, v);
			}
		}
	}
	
	inline void build() {
		dfs(1, -1, 1);
		dfs2(1, 1);
	}
	
	inline vector<pii> get(int x, int y) {
		vector<pii> res;
		while (top[x] != top[y]) {
			if (dep[top[x]] < dep[top[y]]) {
				swap(x, y);
			}
			res.pb(dfn[top[x]], dfn[x]);
			x = fa[top[x]];
		}
		if (dep[x] > dep[y]) {
			swap(x, y);
		}
		res.pb(dfn[x], dfn[y]);
		return res;
	}
} T1, T2;

int p[maxn], q[maxn], bel[maxn], blo, L[maxn], R[maxn], d[maxn];
ull ans[maxn];
struct node {
	int x, y;
	ull k;
} b[maxn];
vector<pii> S[maxn], T[maxn];

namespace BLK {
	ull a[maxn], b[maxn];
	
	inline void update(int l, int r, ull x) {
		if (bel[l] == bel[r]) {
			for (int i = l; i <= r; ++i) {
				a[i] += x;
			}
			return;
		}
		for (int i = l; i <= R[bel[l]]; ++i) {
			a[i] += x;
		}
		for (int i = L[bel[r]]; i <= r; ++i) {
			a[i] += x;
		}
		for (int i = bel[l] + 1; i < bel[r]; ++i) {
			b[i] += x;
		}
	}
	
	inline ull query(int x) {
		return a[x] + b[bel[x]];
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%llu", &a[i]);
	}
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		T1.add_edge(u, v);
	}
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		T2.add_edge(u, v);
	}
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d%llu", &b[i].x, &b[i].y, &b[i].k);
	}
	T1.build();
	T2.build();
	for (int i = 1; i <= n; ++i) {
		p[i] = T1.dfn[T2.rnk[i]];
		c[T1.dfn[i]] = a[i];
	}
	for (int i = 1; i <= n; ++i) {
		a[i] = c[i];
	}
	blo = sqrt(n);
	for (int i = 1; i <= n; ++i) {
		bel[i] = (i - 1) / blo + 1;
		if (!L[bel[i]]) {
			L[bel[i]] = i;
		}
		R[bel[i]] = i;
	}
	for (int i = 1; i <= n; ++i) {
		BLK::update(i, i, a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		S[i] = T1.get(b[i].x, b[i].y);
		T[i] = T2.get(b[i].x, b[i].y);
		for (pii _ : S[i]) {
			BLK::update(_.fst, _.scd, b[i].k);
		}
		for (pii _ : T[i]) {
			int l = _.fst, r = _.scd;
			if (bel[l] == bel[r] || 1) {
				for (int j = l; j <= r; ++j) {
					ans[i] += BLK::query(p[j]);
				}
				continue;
			}
			for (int j = l; j <= R[bel[l]]; ++j) {
				ans[i] += BLK::query(p[j]);
			}
			for (int j = L[bel[r]]; j <= r; ++j) {
				ans[i] += BLK::query(p[j]);
			}
		}
	}
	for (int k = 1; k <= bel[n]; ++k) {
		mems(d, 0);
		for (int i = L[k]; i <= R[k]; ++i) {
			d[p[i]] = 1;
		}
		for (int i = 1; i <= n; ++i) {
			d[i] += d[i - 1];
		}
		ull s = 0;
		for (int i = 1; i <= m; ++i) {
			for (pii _ : S[i]) {
				s += (d[_.scd] - d[_.fst - 1]) * b[i].k;
			}
			for (pii _ : T[i]) {
				int l = _.fst, r = _.scd;
				if (bel[l] < k && k < bel[r]) {
					ans[i] += s;
				}
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		printf("%llu\n", ans[i]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 14ms
memory: 43712kb

input:

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

output:

12105153858659381124
18367442707572066757
11668241962484097878
11288238120352358472
1742468310074622166
9942835997686093671
3305677510569607477
17741602000425004088
14984128302052618266
1075081718074605786
6509217537832509095
16750513627843273113
8569443169249732820
14475184194298579044
156111071108...

result:

wrong answer 42nd lines differ - expected: '14514657051149777936', found: '7004956223442935240'

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: 14
Accepted
time: 3724ms
memory: 90444kb

input:

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

output:

9042998055336671259
11611293489264521142
5835924579879681322
9187084356907537870
17810346410706951073
565636160725988981
837626748701483168
16059573289829807099
7246210357888652619
7725251776483176497
17088098442183693937
9042305714006927228
10907378739216215456
6526772063609981609
51578202456469609...

result:

ok 200000 lines

Test #22:

score: 0
Wrong Answer
time: 5112ms
memory: 90348kb

input:

200000 200000
13175752638648662841 17926176333479943540 18069418271192836667 7662981418770774166 17432280672869071045 9361466030141569604 17336291298429915451 758279154724011577 10229986883918215412 16695796270233481895 1104033984864960726 9768530369533627193 7121962912997584423 8574667967472399164 ...

output:

761007177180158471
13713170416673859892
9085452500188024811
6279851675232444776
9823187704909577710
8445462831147265324
2549519145424583813
12628966555486388857
14265121989865566834
6520346880672680237
13101459183526308131
999924043939340162
18263995506773932901
5204528109864295202
12531805215875429...

result:

wrong answer 2nd lines differ - expected: '99932139211644879', found: '13713170416673859892'

Subtask #5:

score: 0
Time Limit Exceeded

Test #27:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #34:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%