Submission #375788

---

Source Code Expand

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}

struct ETT{//{{{
    struct Node{//{{{
        using Ptr = Node *;
        using NData = tuple<ll, int>;      // node data
        using TData = tuple<ll, int>; // subtree data (calc in 'update')
        NData ndata;
        TData tdata;
        Ptr l, r, p, rev;
        int size;
        Node(const NData &ndata, Ptr l = nullptr, Ptr r = nullptr)
            : ndata(ndata), l(l), r(r), p(nullptr), rev(nullptr), size(1){}
        Ptr &ch(const int &dir){ return dir > 0 ? r : l; }
    };//}}}

    friend ostream &operator<<(ostream &os, const Node *u){
        if(u == nullptr) return os << "nullptr";
        return os << (get<0>(u->ndata) > (1LL<<30) ? "v " : "e ") << get<1>(u->ndata) << "  (" << static_cast<const void*>(u) << ")";
    }

    using NData = Node::NData;
    using TData = Node::TData;
    using Ptr   = Node::Ptr;

    static inline Ptr update(const Ptr &u){
        if(u == nullptr) return u;
        u->size = 1 + size(u->l) + size(u->r);
        // write code here!
        u->tdata = u->ndata;
        if(u->l) chmin(u->tdata, u->l->tdata);
        if(u->r) chmin(u->tdata, u->r->tdata);
        return u;
    }
    static inline Ptr push(const Ptr &u){
        if(u == nullptr) return u;
        // write code here!
        return u;
    }

    static inline int size(const Ptr &u){ return u == nullptr ? 0 : u->size; }
    static inline Ptr new_node(const NData &ndata,
            Ptr l = nullptr, Ptr r = nullptr){
        Ptr u = new Node(ndata);
        add_ch(u, 0, l); add_ch(u, 1, r);
        return update(u);
    }
    static inline void delete_node(Ptr p){ delete p; }
    // splay tree//{{{
    static inline int state(Ptr u){ return u->p ? (u->p->l == u ? -1 : +1) : 0; }
    static inline void rotate(Ptr u){ //{{{
        Ptr p = u->p, pp = p->p;
        if(pp) push(pp); push(p); push(u);
        int lr = state(u);
        if(pp != nullptr) pp->ch(state(p)) = u;
        u->p = pp;
        if(u->ch(-lr)) u->ch(-lr)->p = p;
        p->ch(lr) = u->ch(-lr);
        p->p = u;
        u->ch(-lr) = p;
        update(p); update(u); update(pp);
    }//}}}
    static inline Ptr splay(Ptr u){//{{{
        for(; state(u); rotate(u)) if(int s = state(u) * state(u->p))
            rotate(s == 1 ? u->p : u);
        return u;
    }//}}}
    static inline Ptr add_ch(Ptr p, int dir, Ptr c){//{{{
        push(p);
        if(c) c->p = p;
        p->ch(dir) = c;
        return update(p);
    }//}}}
    static inline Ptr remove_ch(Ptr u, int dir){//{{{
        Ptr v = u->ch(dir);
        if(v != nullptr) u->ch(dir) = v->p = nullptr;
        update(u);
        return v;
    }//}}}
    static inline Ptr join(Ptr u, Ptr v){//{{{
        if(u == nullptr or v == nullptr) return u ? u : v;
        for(splay(u); u->r; u = u->r) void();
        return add_ch(splay(u), 1, splay(v));
    }//}}}
//}}}
    // euler tour tree
    static Ptr add_vertex(const NData &ndata){ return new_node(ndata); }
    static Ptr add_edge(const Ptr &u, const Ptr &v, const NData &ndata){//{{{
        // tr << "link " << u << ", " << v << endl;
        // tr << "u = " << endl; prt(u);
        // tr << "v = " << endl; prt(v);
        splay(u); splay(v);
        Ptr uv = new_node(ndata, u, remove_ch(v, 1));
        Ptr vu = new_node(ndata, v, remove_ch(u, 1));
        uv->rev = vu; vu->rev = uv;
        join(uv, vu);
        // tr << "result = " << endl; prt(uv); tr << endl;
        return uv;
    }//}}}

    //static void prt(Ptr u, int d){
    //    if(u == nullptr) return;
    //    prt(u->l, d+4);
    //    tr << string(d, ' ') << u << endl;
    //    prt(u->r, d+4);
    //}
    //static void prt(Ptr u){
    //    while(u->p) u = u->p;
    //    prt(u, 0);
    //}

    static void remove_edge(Ptr uv){//{{{
        // tr << "cut edge " << uv << endl;
        // tr << "uv =" << endl; prt(uv);
        Ptr vu = uv->rev;
        assert(vu != nullptr && "assert in 'remove_edge': uv is not edge.");
        splay(uv);
        Ptr t = vu;
        while(t->p != uv) t = t->p;
        if(uv->l == t){ swap(uv, vu); splay(uv); }
        // tr << "uv = " << uv << ", vu = " << vu << endl;
        // vu is right of uv. (i.e. after than uv)
        remove_ch(uv, 1);
        Ptr A = join(remove_ch(splay(vu), 1), remove_ch(uv, 0));
        Ptr B = remove_ch(splay(vu), 0);
        // tr << "A =" << endl; prt(A);
        // tr << "B =" << endl; prt(B); tr << endl;
        delete_node(uv); delete_node(vu);
    }//}}}

    static TData get_data(Ptr u){ return splay(u)->tdata; }
    static void set_data(Ptr u, const NData &ndata){
        splay(u)->ndata = ndata;
        update(u);
    }
};//}}}
struct ETTManager{//{{{
    using NData = ETT::NData;
    using TData = ETT::TData;
    using Ptr   = ETT::Ptr;
    vector<ETT::Ptr> vs;
    map<pair<int, int>, ETT::Ptr> es;
    ETTManager(int n, const NData &ndata) : vs(n, nullptr){
        for(auto &v : vs) v = ETT::add_vertex(ndata);
    }
    void add_edge(int u, int v, const NData &ndata){
        es[std::minmax(u, v)] = ETT::add_edge(vs[u], vs[v], ndata);
    }
    void remove_edge(int u, int v){
        const auto &key = std::minmax(u, v);
        ETT::remove_edge(es[key]);
        es.erase(key);
    }
    bool has_edge(int u, int v){ return es.count(std::minmax(u, v)); }
    TData get_data(int u){ return ETT::get_data(vs[u]); }
    void set_data(int u, const NData &ndata){
        ETT::set_data(vs[u], ndata); }
    void set_data(int u, int v, const NData &ndata){
        ETT::set_data(es[std::minmax(u, v)], ndata);
        ETT::set_data(es[std::minmax(u, v)]->rev, ndata);
    }
};//}}}

bool solve(){
    int n;
    cin >> n;
    constexpr ll INF = 1LL<<40;
    ETTManager g(n, make_tuple(INF, INF));
    rep(u, n) g.set_data(u, make_tuple(INF, u));
    vector<tuple<int, int, ll>> es;
    rep(i, n-1){
        int a, b, c;
        cin >> a >> b >> c;
        --a; --b;
        if(a > b) swap(a, b);
        g.add_edge(a, b, make_tuple(c, i));
        es.emplace_back(a, b, c);
    }
    int q;
    cin >> q;
    rep(_, q){
        int op;
        cin >> op;
        if(op == 1){
            int i; ll d; cin >> i >> d; --i;
            get<2>(es[i]) += d;
            if(!g.has_edge(get<0>(es[i]), get<1>(es[i]))) continue;
            g.set_data(get<0>(es[i]), get<1>(es[i]),
                    make_tuple(get<2>(es[i]), i));
        }else{
            int i; cin >> i; --i;
            if(!g.has_edge(get<0>(es[i]), get<1>(es[i]))){
                cout << -1 << endl;
                continue;
            }
            i = get<1>(g.get_data(get<0>(es[i])));
            g.remove_edge(get<0>(es[i]), get<1>(es[i]));
            cout << i+1 << endl;
        }
    }
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result