QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718079 | #9492. 树上简单求和 | Hunster | 0 | 3144ms | 120500kb | C++23 | 8.8kb | 2024-11-06 19:38:34 | 2024-11-06 19:38:34 |
Judging History
answer
#include <bits/stdc++.h>
namespace IO {
#ifdef _DEBUG
constexpr int MAX_SIZE = 1;
#else
constexpr int MAX_SIZE = 1 << 20;
#endif
class Reader {
private:
FILE *file;
char buff[MAX_SIZE], *p1, *p2;
int getchar() {
if (p1 == p2) p2 = (p1 = buff) + fread(buff, 1, MAX_SIZE, file);
return p1 == p2 ? EOF : *p1++;
}
public:
Reader(FILE *_file) {
file = _file;
p1 = p2 = buff;
}
Reader(const char* file_dir) {
file = std::fopen(file_dir, "r");
p1 = p2 = buff;
}
void read() {}
template<typename... Args>
void read(int &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
read(other...);
}
template<typename... Args>
void read(long long &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
read(other...);
}
template<typename... Args>
void read(__int128 &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
read(other...);
}
template<typename... Args>
void read(unsigned int &x, Args &...other) {
int ch;
x = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) ;
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
read(other...);
}
template<typename... Args>
void read(unsigned long long &x, Args &...other) {
int ch;
x = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) ;
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
read(other...);
}
template<typename... Args>
void read(unsigned __int128 &x, Args &...other) {
int ch;
x = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) ;
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
read(other...);
}
template<typename... Args>
void read(double &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (ch == '.') {
double e = 1;
for (ch = getchar(); isdigit(ch); ch = getchar())
x += (ch ^ 48) * (e *= .1);
}
if (f) x = -x;
read(other...);
}
template<typename... Args>
void read(char &ch, Args &...other) {
ch = getchar();
while (!isgraph(ch)) ch = getchar();
read(other...);
}
template<typename... Args>
void read(std::string &s, Args &...other) {
char ch;
s = "";
ch = getchar();
for (; !isgraph(ch);) ch = getchar();
for (; isgraph(ch); ch = getchar()) s += ch;
read(other...);
}
template<typename... Args>
void read(long double &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (ch == '.') {
long double e = 1;
for (ch = getchar(); isdigit(ch); ch = getchar())
x += (ch ^ 48) * (e *= .1);
}
if (f) x = -x;
read(other...);
}
void read(char* s) {
char ch;
ch = getchar();
while (!isgraph(ch)) ch = getchar();
for (; isgraph(ch); ch = getchar()) *s++ = ch;
*s = 0;
}
};
}
IO::Reader reader(stdin);
using LL = long long;
using ULL = unsigned long long;
constexpr int N = 200005;
int n, m;
ULL a[N];
std::vector<int> tree[2][N];
int _fa[N], fa[2][N][20], dep[2][N], dfn[2][N], size[2][N], dfc[2];
template <int o>
void pre_dfs(int u, int p) {
if (o == 1) {
_fa[u] = p;
a[u] += a[p];
}
size[o][u] = 1;
dfn[o][u] = ++dfc[o];
dep[o][u] = dep[o][p] + 1;
fa[o][u][0] = p;
for (int i = 1; i < 20; i++) fa[o][u][i] = fa[o][fa[o][u][i - 1]][i - 1];
for (int v : tree[o][u]) {
if (v == p) continue;
pre_dfs<o>(v, u);
size[o][u] += size[o][v];
}
}
template <int o>
int lca(int x, int y) {
if (dep[o][x] > dep[o][y]) std::swap(x, y);
for (int i = 19; i >= 0; i--) if (dep[o][fa[o][y][i]] >= dep[o][x]) y = fa[o][y][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--) if (fa[o][x][i] != fa[o][y][i]) x = fa[o][x][i], y = fa[o][y][i];
return fa[o][x][0];
}
int tot, key[N], pos[1003];
int get_key(int u, int p) {
int max = 0;
for (int v : tree[1][u]) {
if (v == p) continue;
max = std::max(max, get_key(v, u) + 1);
}
if (max > 600) {
key[u] = ++tot;
pos[tot] = u;
max = 0;
}
return max;
}
std::vector<std::pair<int, ULL>> h[N], g[N], d[1003];
struct Blocks {
ULL h[1003];
ULL g[1003][1003];
int bl[1003], br[1003], bel[N];
void build() {
for (int i = 1; i <= n; i++) bel[i] = (i + 450 - 1) / 450;
for (int i = 1; i <= n; i++) br[bel[i]] = i;
for (int i = n; i >= 1; i--) bl[bel[i]] = i;
}
void add(int x, ULL v) {
int b = bel[x];
for (int i = b; i <= bel[n]; i++) h[i] += v;
for (int i = x; i <= br[b]; i++) g[b][i - bl[b] + 1] += v;
}
ULL query(int x) {
int b = bel[x];
return h[b - 1] + g[b][x - bl[b] + 1];
}
};
Blocks blocks;
ULL ans[N];
int tag[N], val[N];
void dfs(int u, int p) {
val[u] = val[p] + tag[u];
for (int v : tree[0][u]) {
if (v == p) continue;
dfs(v, u);
}
}
int main() {
reader.read(n, m);
for (int i = 1; i <= n; i++) reader.read(a[i]);
for (int i = 1; i < n; i++) {
int x, y;
reader.read(x, y);
tree[0][x].push_back(y);
tree[0][y].push_back(x);
}
for (int i = 1; i < n; i++) {
int x, y;
reader.read(x, y);
tree[1][x].push_back(y);
tree[1][y].push_back(x);
}
pre_dfs<0>(1, 0);
pre_dfs<1>(1, 0);
get_key(1, 0);
for (int i = 1; i <= m; i++) {
int x, y; ULL k;
reader.read(x, y, k);
if (dfn[0][x] > dfn[0][y]) std::swap(x, y);
int p0 = lca<0>(x, y);
h[i].push_back({y, k});
if (x != p0) {
h[i].push_back({x, k});
h[i].push_back({p0, -k});
}
if (fa[0][p0][0]) h[i].push_back({fa[0][p0][0], -k});
if (dfn[1][x] > dfn[1][y]) std::swap(x, y);
int p1 = lca<1>(x, y);
g[i].push_back({y, 1});
if (x != p1) {
g[i].push_back({x, 1});
g[i].push_back({p1, -1});
}
if (fa[1][p1][0]) g[i].push_back({fa[1][p1][0], -1});
ans[i] = a[x] + a[y] - a[p1] - a[fa[1][p1][0]];
}
blocks.build();
for (int i = 1; i <= m; i++) {
for (auto [x, v] : h[i]) blocks.add(dfn[0][x], v);
for (auto [x, v] : g[i]) {
while (x && !key[x]) {
ans[i] += v * (blocks.query(dfn[0][x] + size[0][x] - 1) - blocks.query(dfn[0][x] - 1));
x = _fa[x];
}
// if (x) d[key[x]].push_back({i, v});
}
}
for (int i = 1; i <= tot; i++) {
if (!d[i].size()) continue;
for (int u = pos[i]; u; u = _fa[u]) tag[u] = 1;
dfs(1, 0);
int p = 0;
ULL cur = 0;
for (auto [id, v] : d[i]) {
while (p + 1 <= id) {
p++;
for (auto [x, v] : h[p]) cur += val[x] * v;
}
ans[id] += v * cur;
}
for (int u = pos[i]; u; u = _fa[u]) tag[u] = 0;
}
for (int i = 1; i <= m; i++) printf("%llu\n", ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 6ms
memory: 15264kb
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:
ok 3000 lines
Test #2:
score: 5
Accepted
time: 7ms
memory: 15424kb
input:
3000 3000 1612333876155866602 8538417838700679227 6080765231437578796 17905224638340228394 12270907925903144224 17944105326358594564 17302041033966840611 1006351124625222126 496336153231744288 9393087977687876980 9553975238547373621 9361882717200384390 15051881329169144319 9757999873162420435 882725...
output:
11133131376095771981 7909873024850695144 16250639243139481926 14562550655578101207 8274205996508264973 178549413271904466 2368406276743327913 7464009386554813982 9439464815411774627 1471756740732097060 15201641099137019227 6774030298556871576 18156105511913219667 1553508745644446823 4225137078364117...
result:
ok 3000 lines
Test #3:
score: 0
Wrong Answer
time: 12ms
memory: 17340kb
input:
3000 3000 9709246061666095435 1861649101703072889 10620139893353930613 17635186539135419482 710209455559527146 6075101384669982511 1120305006358459674 9703156967435388252 1397046737759839382 5259056712870179169 8253156305433022999 710199693203327302 15130650033641744675 10720111924616886955 15543351...
output:
1096119423551923889 11888631444934927468 10329991275066593625 11868314225757781613 766758648560863190 2694311067273684659 12845795816837904693 8178319091296518051 9541870901063510320 12681924522026761076 12277724185958011900 2701129734549133184 821624424883547302 4859834102876213962 8976625148435674...
result:
wrong answer 1st lines differ - expected: '7834604406305153073', found: '1096119423551923889'
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: 1471ms
memory: 114352kb
input:
200000 200000 622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...
output:
9042998055336671259 10332533443945436878 5835924579879681322 18036061039738468170 6933818974509245493 9414612843556919281 837626748701483168 16059573289829807099 16095187040719582919 7725251776483176497 7490331051305072621 17891282396837857528 921598232438272980 1199909091134114973 51578202456469609...
result:
wrong answer 2nd lines differ - expected: '11611293489264521142', found: '10332533443945436878'
Subtask #5:
score: 0
Wrong Answer
Test #27:
score: 0
Wrong Answer
time: 3144ms
memory: 117752kb
input:
200000 200000 1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...
output:
13173833545015224305 13500485507263446238 9699190208173499079 15502455369091483544 14175915495441126999 332099717342328587 7616149028141438708 6103825049622420361 9190582745480082754 12076902367456193772 16246726222913687839 14382740819364937117 10815839056328109887 7786879116146301090 1787597175705...
result:
wrong answer 1st lines differ - expected: '11479812171669345085', found: '13173833545015224305'
Subtask #6:
score: 0
Wrong Answer
Test #34:
score: 0
Wrong Answer
time: 846ms
memory: 120500kb
input:
200000 200000 6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...
output:
3928755536648352396 4819126343150520704 17240340500602641545 8211142070525812081 12630908431695442870 7063776058340842765 13357695842393071909 6180399980461911951 15448932131447796013 10826607922115624173 1977725848578007798 7525670755410919533 14656268213532799923 3411932465569839055 22671520068072...
result:
wrong answer 1st lines differ - expected: '5519324519442957729', found: '3928755536648352396'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%