QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80135#5439. Meet in the MiddleAPJifengcWA 39ms57060kbC++205.2kb2023-02-22 15:54:192023-02-22 15:54:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-22 15:54:22]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:57060kb
  • [2023-02-22 15:54:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q;
struct Tree {
#define forGraph(u, v) for (int i = fst[u], v = to[i]; i; i = nxt[i], v = to[i])
    int fst[MAXN], to[MAXN], nxt[MAXN], w[MAXN], tot;
    void add(int u, int v, int ww) {
        to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot, w[tot] = ww;
    }
};
struct Tree1 : public Tree {
    int dfn[MAXN], idf[MAXN], dcnt;
    int dep[MAXN];
    int st[MAXN][20];
    long long dis[MAXN];
    void dfs(int u, int pre) {
        dfn[u] = ++dcnt, idf[dcnt] = u;
        dep[u] = dep[pre] + 1;
        forGraph(u, v) if (v != pre) {
            dis[v] = dis[u] + w[i];
            dfs(v, u);
            idf[++dcnt] = u;
        }
    }
    void build() {
        for (int i = 1; i <= dcnt; i++)
            st[i][0] = idf[i];
        for (int j = 1; j <= 18; j++) {
            for (int i = 1; i + (1 << j) - 1 <= dcnt; i++) {
                st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) ? 
                    st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    int lca(int u, int v) {
        int l = dfn[u], r = dfn[v];
        if (l > r) swap(l, r);
        int len = __lg(r - l + 1);
        return dep[st[l][len]] < dep[st[r - (1 << len) + 1][len]] ? 
            st[l][len] : st[r - (1 << len) + 1][len];
    }
    long long dist(int u, int v) {
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }
} t1;
struct SegmentTree {
    struct Chain {
        pair<int, long long> u, v;
        long long dist;
        inline Chain() : u(), v(), dist(0) {}
        inline Chain(pair<int, long long> u, pair<int, long long> v) : u(u), v(v) {
            dist = t1.dist(u.first, v.first) + u.second + v.second;
        }
        inline bool operator<(const Chain &b) const {
            return dist < b.dist;
        }
        inline Chain operator+(const Chain &b) const {
            if (!u.first && !v.first) return b;
            if (!b.u.first && !b.v.first) return *this;
            Chain c = max(*this, b);
            for (auto x : {u, v}) if (x.first) {
                for (auto y : {b.u, b.v}) if (y.first) {
                    c = max(c, Chain(x, y));
                }
            }
            return c;
        }
    };
    struct Node {
        Chain chain;
        int tag;
    } t[MAXN << 2];
    #define lc (i << 1)
    #define rc (i << 1 | 1)
    void tag(int i, int v) {
        t[i].tag += v;
        t[i].chain.u.second += v;
        t[i].chain.v.second += v;
        t[i].chain.dist += 2 * v;
    }
    void pushDown(int i) {
        if (t[i].tag) {
            tag(lc, t[i].tag);
            tag(rc, t[i].tag);
            t[i].tag = 0;
        }
    }
    void pushUp(int i) {
        t[i].chain = t[lc].chain + t[rc].chain;
    }
    void build(int *idf, long long *dis, int i = 1, int l = 1, int r = n) {
        if (l == r) {
            t[i].chain.u.first = idf[l];
            t[i].chain.u.second = dis[idf[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(idf, dis, lc, l, mid);
        build(idf, dis, rc, mid + 1, r);
        pushUp(i);
    }
    void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
        if (a <= l && r <= b) {
            tag(i, v);
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(i);
        if (a <= mid) add(a, b, v, lc, l, mid);
        if (b > mid) add(a, b, v, rc, mid + 1, r);
        pushUp(i);
    }
} st;
long long ans[MAXN];
struct Tree2 : public Tree {
    long long dis[MAXN];
    int dfn[MAXN], ed[MAXN], idf[MAXN], dcnt;
    void dfs1(int u, int pre) {
        dfn[u] = ++dcnt, idf[dcnt] = u;
        forGraph(u, v) if (v != pre) {
            dis[v] = dis[u] + w[i];
            dfs1(v, u);
        }
        ed[u] = dcnt;
    }
    void build() {
        st.build(idf, dis);
    }
    vector<pair<int, int>> qs[MAXN];
    void dfs2(int u, int pre) {
        for (auto p : qs[u]) {
            ans[p.first] = max(
                t1.dist(st.t[1].chain.u.first, p.second) + st.t[1].chain.u.second,
                t1.dist(st.t[1].chain.v.first, p.second) + st.t[1].chain.v.second
            );
        }
        forGraph(u, v) if (v != pre) {
            st.add(1, n, w[i]);
            st.add(dfn[v], ed[v], -2 * w[i]);
            dfs2(v, u);
            st.add(1, n, -w[i]);
            st.add(dfn[v], ed[v], 2 * w[i]);
        }
    }
} t2;
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i < n; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        t1.add(u, v, w);
        t1.add(v, u, w);
    }
    t1.dfs(1, 0);
    t1.build();
    for (int i = 1; i < n; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        t2.add(u, v, w);
        t2.add(v, u, w);
    }
    t2.dfs1(1, 0);
    t2.build();
    for (int i = 1; i <= q; i++) {
        int a, b; scanf("%d%d", &a, &b);
        t2.qs[b].push_back({i, a});
    }
    t2.dfs2(1, 0);
    for (int i = 1; i <= q; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

/*
3 4
1 2 1
2 3 2 
1 2 2
2 3 1
1 1
1 2
2 1
2 2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 52744kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 5ms
memory: 57060kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 5ms
memory: 52756kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 39ms
memory: 56584kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

756171780984
630834760472
518568909000
745399789278
452428534374
754176312100
801732359852
589153328707
648376542766
808170418762
834565050580
739059014212
749157782737
768073360812
713694385754
686938325353
631536005150
849744747636
709355803416
731106405456
657429211416
671056959258
701575393972
7...

result:

wrong answer 1st numbers differ - expected: '647838384844', found: '756171780984'