#117923 (C++11) No.235 めぐるはめぐる (5)

提出ソース
結果

問題	No.235 めぐるはめぐる (5)
ユーザー	はむこ
提出日時	2016-09-19 20:32:17
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2,483 ms / 10,000 ms
コード長	10,270 bytes
コンパイル時間	2,085 ms
コンパイル使用メモリ	179,900 KB
実行使用メモリ	61,692 KB
最終ジャッジ日時	2024-11-17 09:57:26
合計ジャッジ時間	12,135 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,483 ms 61,592 KB
testcase_01	AC	1,616 ms 61,692 KB
testcase_02	AC	2,260 ms 61,164 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>

using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
typedef long long LL;
typedef vector<int> vll;
typedef vector<vll> vvll;
typedef vector<vll> Graph;

template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args> 
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; cout << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const unordered_map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }

struct INIT {INIT() {ios::sync_with_stdio(false);cin.tie(0);}}init;

// heavy light decomposition
//
// 今までの番号を、Heavy-Lightパスの根から葉の方向へと付け替える in [0, n)
// これ自体にはデータを載せず、パスの添字のみを取得するインターフェースのみ提供
class HLD {
    private:
        vector<int> treesize; // tree->size(): 子の数
        Graph *tree;
    public:
        // i: ノードの添字
        // j: Heavy pathの添字
        int size = 0; // Heavy pathの数
        vector<int> group; // tree->size(): ノードiが属するグループj
        vector<int> id; // tree->size(): ノードiに再割り振りされた新ノード番号id in [0, tree->size())
        vector<int> par; // size: Heavy path jの根の親のノードi
        vector<int> bg; //  size: Heavy path jの根のノードi
    private:
        void setTreeSize(int v) {
            treesize[v]=1;
            for (auto &u:(*tree)[v]) {
                setTreeSize(u);
                treesize[v]+=treesize[u];
            }
        }
        void build(int v, int g, int& i) {
            group[v]=g;
            id[v]=i++;
            Graph &gr=(*tree);
            if (!gr[v].size()) return;

            // 最大サイズの子hを求める
            int h=gr[v][0]; 
            for (auto &u:gr[v])
                if(treesize[h]<treesize[u])h=u;

            // Heavy
            build(h, g, i);

            // Light
            for (auto &u:gr[v]) if(h != u) { 
//                cout << v << " " << h <<  " " << u << " " << size << "#light" << endl;
                par.push_back(v);
                bg.push_back(i);
                /*
                par[size]=v;
                bg[size]=i;
                */
                build(u, size++, i);
            }
        }
    public:
        HLD(Graph *tree, int root=0) : tree(tree){
            int n = tree->size();
            treesize.resize(n);
            group.resize(n);
            id.resize(n);

            setTreeSize(root);
            int i=0; // 再度割り振り直す添字番号
            par.push_back(-1);
            bg.push_back(i);
            build(root, size++, i);
        }
        // O(log n)
        //
        // [r, c]の再割り振りされた添字区間を返す。
        //
        // rがcより根側である必要がある
        // c側から、以下の漸化式によってパスを分解する
        //      ret += {groupの根, c}, c = groupの根の親
        using P=pair<int, int>;
        vector<P> decomposition(int r, int c) {
            vector<P> res;
            while (group[c]!=group[r]) {
                res.push_back(P(bg[group[c]], id[c]));
                c=par[group[c]];
            }
            res.push_back(P(id[r], id[c]));
            return res;
        }
        void print(void) {
            rep(i, tree->size()) {
                cout << group[i] << " " << id[i] << endl;
            }
            cout << "####" << endl;
            rep(i, size) {
                cout << par[i] << " " << bg[i] << endl;
            }
        }

};

void make_tree(int v, Graph& G, vll& Par, vll& D,  Graph& C) {
    for (auto &e:G[v]) {
        if(e!=Par[v]) {
            C[v].push_back(e);
            D[e]=D[v]+1;
            Par[e]=v;
            make_tree(e, G, Par, D, C);
        }
    }
}


//lcaの準備
void build_PP(vll& P, vector<vll>& PP) {
    int N = P.size();
    for (int i = 0; i < N; i++)PP[0][i] = P[i];
    for (int k = 0, f=1;f; k++) {
        f=0;
        for (int i = 0; i < N; i++) {
            if(PP[k][i]<0)PP[k+1][i]=-1;
            else  {PP[k+1][i]=PP[k][PP[k][i]];f=1;}
        }
    }
}
int lca(int u, int v, vll& D, vector<vll> &PP) {
    if(D[u] > D[v])swap(u, v);
    for (int k = 0, d;(d=D[v]-D[u]); k++)if((d  >>  k) & 1)v=PP[k][v];
    if(u==v)return v;
    for (int k = PP.size() - 1; k >=0 ; k--) {
        if(PP[k][u]!=PP[k][v]) {
            u=PP[k][u];
            v=PP[k][v];
        }
    }
    return PP[0][u];
}


#define SIZE 900000
#define L(v) (v*2+1)
#define R(v) (v*2+2)
#define SET 0
#define ADD 1
#define GET 2

typedef LL val;
const LL MOD=1e9+7;
struct node {
    int bg, ed;
    val v, add, sum;
    inline val getval() {
        return (v+sum*add%MOD)%MOD;
    }
    inline void init(int b, int e) {
        bg =b, ed=e;
        v=0, add=0, sum=0;
    }
    bool isleaf() {return bg==ed;}
}mem[SIZE];
inline val comb(val l, val r) {
    return (l+r)%MOD;
}
class segTree {
    private:
        node *t;
        val make_tree(int bg, int ed, vector<int> &c, vector<int> &s, int v=0) {
            node *p=t+v;
            p->init(bg, ed);
            if(!p->isleaf()) {
                int m=(bg+ed)/2;
                p->sum+=make_tree(bg, m, c, s, L(v));
                p->sum+=make_tree(m+1, ed, c, s, R(v));
                p->sum%=MOD;
                update(v);
            } else {
                p->sum=c[bg];
                p->v=s[bg];
            }
            return p->sum;
        }
    public:
        using P=pair<int, int>;
        segTree(int bg, int ed, vector<int> &c, vector<int> &s):t(mem) {
            make_tree(bg, ed, c, s);
        }
        inline void lazy_update(int v) {
            node *p=t+v, *l=t+L(v), *r=t+R(v);
            if(p->isleaf())return;
            (l->add+=p->add)%=MOD;
            (r->add+=p->add)%=MOD;
            p->add=0;
        }
        inline void update(int v) {
            node *p=t+v, *l=t+L(v), *r=t+R(v);
            if(p->isleaf()) {
                p->v+=p->add*p->sum%MOD;
                p->v%=MOD;
                p->add=0;
            }
            else {
                p->v=comb(l->getval(), r->getval());
            }
        }
        val treat(int type, int bg, int ed, val x, int v=0) {
            node *p=t+v, *l=t+L(v), *r=t+R(v);
            lazy_update(v);
            if(P(bg, ed)==P(p->bg, p->ed)) {
                if(type==ADD)(p->add+=x)%=MOD;
                update(v);
                return p->getval();
            }
            int m;
            val res=0;
            if(bg<=(m=min(ed, l->ed)))
                res=comb(res, treat(type, bg, m, x, L(v)));
            if((m=max(bg, r->bg))<=ed)
                res=comb(res, treat(type, m, ed, x, R(v)));
            update(v);
            return res;
        }
        val get(int bg, int ed) {
            return treat(GET, bg, ed, val());
        }
        val add(int bg, int ed, val x) {
            return treat(ADD, bg, ed, x);
        }
};
const int root=0;
int main() {
    int N;cin >> N;
    N++;
    vector<int> s(N), S(N), c(N), C(N);
    s[root]=c[root]=0;
    for (int i=1;i<N;i++) cin >> s[i];
    for (int i=1;i<N;i++) cin >> c[i];
    Graph g(N), tree(N);
    g[root].push_back(1);
    vll par(N, -1), depth(N, 0);
    for (int i=2;i<N;i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    make_tree(root, g, par, depth, tree);

    vector<vll> pp(18, vll(N, -1)); // LCA用ダブリング
    build_PP(par, pp);

    HLD hld(&tree, root);
    /*
    cout << endl;
    cout << "########" << endl;
    hld.print();
    cout << "########" << endl;
    */
    for (int i=0;i<N;i++) {
        S[hld.id[i]]=s[i];
        C[hld.id[i]]=c[i];
    }
    segTree st(0, N-1, C, S);
    int Q;
    cin >> Q;
    while (Q--) {
        int t;
        cin >> t;
        if(t) {
            int x, y;
            cin >> x >> y;
            int ca=lca(x, y, depth, pp);
            LL ans=0;
            auto p=hld.decomposition(ca, x);
            auto q=hld.decomposition(ca, y);
            auto r=hld.decomposition(ca, ca);
            for (auto &it:p)(ans+=st.get(it.first, it.second))%=MOD;
            for (auto &it:q)(ans+=st.get(it.first, it.second))%=MOD;
            for (auto &it:r)ans+=MOD-st.get(it.first, it.second);
            cout<<ans%MOD<<endl;
        } else {
            int x, y, z;
            cin >> x >> y >> z;
            int ca=lca(x, y, depth, pp);
            auto p=hld.decomposition(ca, x);
            auto q=hld.decomposition(ca, y);
            auto r=hld.decomposition(ca, ca);
            for (auto &it:p)st.add(it.first, it.second, z);
            for (auto &it:q)st.add(it.first, it.second, z);
            for (auto &it:r)st.add(it.first, it.second, MOD-z);
        }
    }
    return 0;
}
yukicoder

結果

テストケース

ソースコード
