QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#666855 | #9492. 树上简单求和 | zlt | 0 | 5112ms | 90444kb | C++14 | 3.9kb | 2024-10-22 20:13:43 | 2024-10-22 20:13:43 |
Judging History
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%