QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717945#9492. 树上简单求和Hunster0 3963ms128604kbC++238.8kb2024-11-06 19:20:222024-11-06 19:20:24

Judging History

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

  • [2024-11-06 19:20:24]
  • 评测
  • 测评结果:0
  • 用时:3963ms
  • 内存:128604kb
  • [2024-11-06 19:20:22]
  • 提交

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

constexpr int B = 700;
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 == B) {
        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 + B - 1) / B;
        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++) {
    //     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: 15424kb

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: 12ms
memory: 15352kb

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: 10ms
memory: 17696kb

input:

3000 3000
9709246061666095435 1861649101703072889 10620139893353930613 17635186539135419482 710209455559527146 6075101384669982511 1120305006358459674 9703156967435388252 1397046737759839382 5259056712870179169 8253156305433022999 710199693203327302 15130650033641744675 10720111924616886955 15543351...

output:

10135056183281053873
14480056066299013956
4948044411307009695
10976597931362127697
11738443613476099310
2634456031161908051
14038370716212123557
13515164814425439399
4024206555043155291
4387970844623580028
11642805469843844638
16764682282380318054
3321057037411886173
4859834102876213962
177960930735...

result:

wrong answer 1st lines differ - expected: '7834604406305153073', found: '10135056183281053873'

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: 1672ms
memory: 120624kb

input:

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

output:

9042998055336671259
11611293489264521142
5835924579879681322
18036061039738468170
17810346410706951073
9414612843556919281
837626748701483168
16059573289829807099
16095187040719582919
7725251776483176497
16542077093879342809
8496284365702576100
706890680306741612
14773028078410059381
515782024564696...

result:

wrong answer 4th lines differ - expected: '9187084356907537870', found: '18036061039738468170'

Subtask #5:

score: 0
Wrong Answer

Test #27:

score: 0
Wrong Answer
time: 3963ms
memory: 128432kb

input:

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

output:

10177736127127414609
14553711178928334604
11275797400633730707
13767737836057500564
435121864270560653
810754199105545601
4723263622533095165
13304567789044188297
6397438217108454232
14555552437541646813
11786074236726548843
9403761854145127294
897659802715130223
13014949761936904840
896577201726740...

result:

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

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 958ms
memory: 128604kb

input:

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

output:

3928755536648352396
5551394301188065075
17240340500602641545
2672263415977310005
5201007965051443062
11437576782916700817
15244544258822061543
6180399980461911951
5005365627116244757
6193380118910780597
6332815561885537536
2276570162994542253
2186217110877573214
5878556741419049750
18060282967307797...

result:

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

Subtask #7:

score: 0
Skipped

Dependency #1:

0%