読者です 読者をやめる 読者になる 読者になる

RUPC参加記1日目

RUPCに参加しました。

1日目は立命館セットで、evimaさんとNOxさんと出ました

がーっと時系列で書くと

Bをevimaさんがコーディング
AはNOxさんがコーディング
Aが♨️したためDをevimaさんがコーディング
僕とNOxさんでAをデバッグしたら日本語読解に失敗していることが判明
Dが♨️、Aに交代
AをAC、僕がCをコーディング
CをAC、Dは♨️
Dは♨️、Fを考える
DがAC、Eをevimaさんがコーディング
Eが♨️、Eのバグ取りとFのコーディングを並列
Fはコーディングが終了、バグ
EがAC、Fのライブラリ写しミスが無いか確認してもらう
ライブラリの4行目ぐらいでいきなりミスってた、目が
直したら51/57ケース通ってRE、ほかにも同じところで落ちている人がいたのでStack overflowの疑いが持ち上がる
よく考えたらLC木の方は簡単に再帰を消せたがまだ通らない、終了(LCAを求める方でdfsをしていた)
Fのコード

#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <stack>

using namespace std;
typedef long long ll;

struct LCNode {
    typedef LCNode* NP;
    static LCNode last_d;
    static NP last;
    NP p, l, r;
    int sz;
    inline int pos() {
        if (p) {
            if (p->l == this) return -1;
            if (p->r == this) return 1;
        }
        return 0;
    }
    void rot() {
        NP qq = p->p;
        int pps = p->pos();
        if (p->l == this) {
            p->l = r; r->p = p;
            r = p; p->p = this;
        } else {
            p->r = l; l->p = p;
            l = p; p->p = this;
        }
        p->update(); update();
        p = qq;
        if (!pps) return;
        if (pps == -1) {
            qq->l = this;
        } else {
            qq->r = this;
        }
        qq->update();
    }
    void splay() {
        supush();
        int ps;
        while ((ps = pos())) {
            int pps = p->pos();
            if (!pps) {
                rot();
            } else if (ps == pps) {
                p->rot(); rot();
            } else {
                rot(); rot();
            }
        }
    }
    void expose() {
        NP u = this, ur = last;
        do {
            u->splay();
            u->r = ur;
            u->update();
            ur = u;
        } while ((u = u->p));
        splay();
    }
    void supush() {
        stack<NP> s;
        NP n = this;
        while (n->pos()) {
            s.push(n);
            n = n->p;
        }
        n->push();
        while (!s.empty()) {
            NP nn = s.top(); s.pop();
            nn->push();
        }
//        if (pos()) {
//            p->supush();
//        }
//        push();
    }

    void link(NP r) {
        expose();
        r->expose();
        p = r;
    }

    typedef ll D;
    D d0, d1;
    D sm0, sm1;
    LCNode(bool f) : p(nullptr), l(last), r(last), sz(1) {
        d0 = d1 = sm0 = sm1 = 0;
    }
    LCNode() : l(nullptr), r(nullptr), sz(0) {}
    void push() {
    }
    void update() {
        sz = 1+l->sz+r->sz;
        sm0 = d0;
        sm1 = d1;
        if (l->sz) {
            sm0 += l->sm0;
            sm1 += l->sm1;
        }
        if (r->sz) {
            sm0 += r->sm0;
            sm1 += r->sm1;
        }
    }
    void add0(D x) {
        expose();
        d0 += x;
        sm0 += x;
    }  
    void add1(D x) {
        expose();
        d1 += x;
        sm1 += x;
    } 
    D get0() {
        expose();
        return sm0;
    }
    D get1() {
        expose();
        return sm1;
    }
};
LCNode LCNode::last_d = LCNode();
LCNode::NP LCNode::last = &last_d;

template<int V>
struct LCA {
    const static int LG = 25;
    int ro[LG][V];
    int dps[V];
    vector<int> g[V];
    void add(int i, int j) {
        g[i].push_back(j);
        g[j].push_back(i);
    }
    /*void dfs(int p, int b) {
        ro[0][p] = b;
        dps[p] = (b == -1) ? 0 : dps[b]+1;
        for (int d: g[p]) {
            if (d == b) continue;
            dfs(d, p);
        }
    }*/
    void init() {
        memset(ro, -1, sizeof(ro));
    }
    void exec(int r) {
//        memset(ro, -1, sizeof(ro));
        //dfs(r, -1);
        for (int i = 0; i < LG-1; i++) {
            for (int j = 0; j < V; j++) {
                ro[i+1][j] = (ro[i][j] == -1) ? -1 : ro[i][ro[i][j]];
            }
        }
    }

    int query(int l, int r) {
        if (dps[l] < dps[r]) swap(l, r);
        int dd = dps[l] - dps[r];
        for (int i = LG-1; i >= 0; i--) {
            if (dd < (1<<i)) continue;
            dd -= 1<<i;
            l = ro[i][l];
        }
        if (l == r) return l;
        for (int i = LG-1; i >= 0; i--) {
            if (ro[i][l] == ro[i][r]) continue;
            l = ro[i][l]; r = ro[i][r];
        }
        return ro[0][l];
    }
};

const int MN = 300300;
LCNode tr[MN];
LCA<MN> lca;
int root[MN];
ll dps[MN];

ll sum(int a) {
//    printf("sum0 %d %lld\n", a, tr[a].get0());
//    printf("sum1 %d %lld\n", a, tr[a].get1());
    return tr[a].get0()*dps[a] - tr[a].get1();
}

int main() {
    lca.init();
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        tr[i] = LCNode(true);
    }
    for (int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        lca.add(a, b);
        tr[b].link(&tr[a]);
        root[b] = a;
    }
    lca.ro[0][0] = -1;
    for (int i = 1; i < n; i++) {
        lca.ro[0][i] = root[i]; 
        lca.dps[i] = dps[i] = dps[root[i]]+1;
    }
    lca.exec(0);
    for (int i = 0; i < q; i++) {
        int t; ll a, b;
        scanf("%d %lld %lld", &t, &a, &b);
        if (t == 0) {
            int d = lca.query(a, b);
//            printf("lca %lld %lld %d\n", a, b, d);
//            printf("lcad %lld %lld %lld\n", sum(a), sum(b), sum(d));
            printf("%lld\n", sum(a)+sum(b)-2*sum(d));
        } else {
            tr[a].add0(b);
            tr[a].add1(dps[a]*b);
        }
    }
    return 0;
}