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

HackerRank Weekly12 White Falcon

Programming Problems and Competitions :: HackerRank
問題は登録しないと見れなかったりするのかな?

問題概要

N頂点のツリーが与えられる、頂点はそれぞれf(x) = ax+bという形で表せる関数を持っている
二種類のクエリが飛んでくる
クエリ1.変更
u, v, a, bが与えられるので、u-vパス間の(両端含む)頂点の持つ関数をすべてf(x) = ax+bに変更する
クエリ2.取得
u, v, xが与えられるので、u-vパス間の(両端含む)頂点をp1, p2, p3, ..., pkとして
f_k( f_k-1( f_k-2( ... f2( f1(x)) ...)))
を求める、ただしf1,f2...fkはp1,p2, ...pkの持つ関数
値は大きくなるのでMod1e9+7で求める

解法

これは木のパスに関する問題ですね。
木のパス…?これはもしかしてLC Tree待ったなしじゃない…?
頂点の値の設定取得遅延評価,evert, linkを実装すると解ける
212行で思ったほどは多くならなかった

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <cassert>
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MD = 1e9+7;
static const P e = P(1, 0);
static const P DEF = P(-1, 0);
P mulp(P l, P r) {
    P res;
    res.first = (l.first*r.first) % MD;
    res.second = ((l.first*r.second)+l.second) % MD;
    return res;
}
P powp(P p, int k) {
    P r = e;
    while (k) {
        if (k & 1) {
            r = mulp(r, p);
        }
        p = mulp(p, p);
        k >>= 1;
    }
    return r;
}

typedef pair<ll, ll> P;
struct LCTree {
    typedef P D;
    struct Node;
    typedef Node* NP;
    static Node last_d;
    static NP last;
    struct Node {
        NP p, l, r;
        int sz;
        bool rev;
        D v, fsm, bsm, lz;
        Node(D v) :p(NULL), l(last), r(last), sz(1), rev(false), v(v), fsm(v), bsm(v), lz(DEF) {}
        Node(NP l, NP r) : l(l), r(r), sz(0), v(e), fsm(e), bsm(e), lz(DEF) {}
        inline int pos() {
            if (p && p->l == this) return -1;
            if (p && p->r == this) return 1;
            return 0;
        }
        void rot() {
            NP q = p, qq = q->p;
            int qp = q->pos();
            if (q->l == this) {
                q->l = r; r->p = q;
                r = q; q->p = this;
            } else {
                q->r = l; l->p = q;
                l = q; q->p = this;
            }
            q->update(); update();
            p = qq;
            if (!qp) return;
            if (qp == -1) {
                qq->l = this;
            } else {
                qq->r = this;
            }
            qq->update();
        }
        void splay() {
            supush();
            while (pos()) {
                int u = pos()*p->pos();
                if (!u) {
                    rot();
                } else if (u == 1) {
                    p->rot(); rot();
                } else {
                    rot(); rot();
                }
            }
        }
        void expose() {
            assert(this != last);
            NP u = this;
            do {
                u->splay();
            } while ((u = u->p));
            u = last;
            u->p = this;
            do {
                u->p->r = u;
                u->p->update();
                u = u->p;
            } while (u->p);
            splay();
        }
        void push() {
            assert(this != last);
            if (rev) {
                swap(l, r);
                if (l->sz) {
                    l->revdata();
                }
                if (r->sz) {
                    r->revdata();
                }
                rev = false;
            }
            if (lz != DEF) {
                if (l->sz) {
                    l->lzdata(lz);
                }
                if (r->sz) {
                    r->lzdata(lz);
                }
                lz = DEF;
            }
        }
        void supush() {
            if (pos()) {
                p->supush();
            }
            push();
        }
        void revdata() {
            rev ^= true;
            swap(fsm, bsm);
        }
        void lzdata(D d) {
            v = d;
            fsm = bsm = powp(d, sz);
            lz = d;
        }
        NP update() {
            if (this == last) return this;
            sz = 1+l->sz+r->sz;
            fsm = mulp(l->fsm, mulp(v, r->fsm));
            bsm = mulp(r->bsm, mulp(v, l->bsm));
            return this;
        }
    } *n;
    LCTree() : n(last) {}
    LCTree(NP n) : n(n) {}
    LCTree(D d) : n(new Node(d)) {}
    int sz() {
        return n->sz;
    }
    void evert() {
        n->expose();
        n->revdata();
    }
    void link(LCTree r) {
        n->expose();
        r.n->expose();
        assert(n->l == last);
        n->p = r.n;
    }
    void set(D x) {
        n->expose();
        n->lzdata(x);
    }
    D get() {
        n->expose();
        return n->fsm;
    }
};
LCTree::Node LCTree::last_d = LCTree::Node((NP)NULL, NULL);
LCTree::NP LCTree::last = &last_d;

const int MN = 50200;

ll a[MN];
LCTree tr[MN];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        tr[i] = LCTree(P(a, b));
    }
    for (int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d %d", &a, &b); a--; b--;
        tr[a].evert();
        tr[a].link(tr[b]);
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int t, u, v;
        scanf("%d %d %d", &t, &u, &v); u--; v--;
        if (t == 1) {
            int a, b;
            scanf("%d %d", &a, &b);
            tr[u].evert();
            tr[v].set(P(a, b));
        } else {
            ll x;
            scanf("%lld", &x);
            tr[v].evert();
            P p = tr[u].get();
            printf("%lld\n", (x*p.first % MD + p.second) % MD);
        }
    }
    return 0;
}