#235213 (C++14) No.650 行列木クエリ

提出ソース
結果

問題	No.650 行列木クエリ
ユーザー	walkre
提出日時	2018-02-10 00:53:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,926 bytes
コンパイル時間	3,814 ms
コンパイル使用メモリ	225,700 KB
実行使用メモリ	84,156 KB
最終ジャッジ日時	2024-10-09 09:09:04
合計ジャッジ時間	6,964 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	AC	2 ms 6,820 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	RE	-
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	314 ms 21,504 KB
testcase_09	AC	947 ms 84,156 KB
testcase_10	RE	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

template<class segment_type,class connection_type> struct HeavyLightDecomposer{
    const vector<vector<int>> graph;
    const int root,n;
    vector<int> parent,subtree_size,depth,
                first,last,prev,next,path_id,local_index;
    vector<vector<int>> paths,children;

    vector<segment_type> segments; //pathに乗っけるデータ構造用
    vector<connection_type> connections; //pathとpathを接続する辺に対応する

    HeavyLightDecomposer(const vector<vector<int>> &graph,int root):graph(graph),root(root),n(graph.size()),
    parent(n),subtree_size(n,1),depth(n),first(n),last(n),prev(n,-1),next(n,-1),path_id(n),local_index(n)
    {
        preprocess();
        decompose();
        segments.resize(paths.size());
        connections.resize(paths.size());
    }

    void preprocess(){
        stack<tuple<int,int,int>> dfs_stack;
        dfs_stack.push(make_tuple(root,-1,0));
        while(!dfs_stack.empty()){
            auto t=dfs_stack.top();
            dfs_stack.pop();
            int v=get<0>(t),p=get<1>(t),i=get<2>(t);
            if(i==0){
                if(v!=root) depth[v]=depth[p]+1;
                dfs_stack.push(make_tuple(v,p,1));
                for(int u:graph[v]){
                    if(u==p) continue;
                    dfs_stack.push(make_tuple(u,v,0));
                }
            }else{
                parent[v]=p;
                for(int u:graph[v]){
                    if(u==p) continue;
                    subtree_size[v]+=subtree_size[u];
                }
            }
        }
    }
    using pii=pair<int,int>;
    void decompose(){
        int cnt=0;
        stack<pii> dfs_stack;
        dfs_stack.push(make_pair(root,0));
        while(!dfs_stack.empty()){
            auto p=dfs_stack.top();
            dfs_stack.pop();

            int v=p.first,id=p.second;
            if(paths.size()<=cnt) paths.resize(cnt+1);
            if(children.size()<=cnt) children.resize(cnt+1);

            int cur=v;
            while(cur!=-1){
                paths[id].push_back(cur);
                int heavy_edge=-1;
                for(int u:graph[cur]){
                    if(u==parent[cur]) continue;
                    if(heavy_edge==-1 and subtree_size[u]*2>=subtree_size[cur]-1) heavy_edge=u;
                    else{
                        ++cnt;
                        children[id].push_back(cnt);
                        dfs_stack.push(make_pair(u,cnt));
                    }
                }
                cur=heavy_edge;
            }
            for(int i=0; i<paths[id].size(); ++i){
                int u=paths[id][i];
                first[u]=paths[id].front();
                last[u]=paths[id].back();
                if(i!=0) prev[u]=paths[id][i-1];
                if(i!=paths[id].size()-1) next[u]=paths[id][i+1];
                path_id[u]=id;
                local_index[u]=i;
            }
        }
    }

    int size()const{
        return n;
    }

    int go_up(int v){ //vが含まれるpathの先頭のノードの親のglobal_indexを返す
        return parent[first[v]];
    }

    int lca(int u,int v){
        while(path_id[u]!=path_id[v]){
            if(depth[first[u]]<depth[first[v]]) v=go_up(v);
            else u=go_up(u);
        }
        return depth[u]<depth[v]?u:v;
    }

    //O(log_2(n))
    int highest_child(int path_id,int idx){ //local indexがidx以下のノードに接続されている子パスの中で最も上にあるもののchildren[path_id]中でのindex
        int lb=-1,ub=children[path_id].size();
        while(ub-lb>1){
            int m=(lb+ub)/2;
            if(local_index[go_up(paths[children[path_id][m]].front())]>=idx) ub=m;
            else lb=m;
        }
        return ub;
    };
};

template<class T,T op(T,T)> class segtree{
public:
    int n,size_;
    vector<T> dat;
    T id_;
    segtree()=default;
    segtree(int size,T id,T initial_value){ init(size,id,initial_value); }
    void init(int size,T id,T initial_value){
        size_=size;
        id_=id;
        n=1;
        while(n<size) n*=2;
        dat.assign(2*n-1,id);
        for(int i=0; i<size; ++i) update(i,initial_value);
    }
    int size()const{ return size_; }
    void update(int k, T a) {
        k+=n-1; // leaf
        dat[k]=a;
        while(k>0) {
            k=(k-1)/2;
            dat[k]=op(dat[k*2+1],dat[k*2+2]);
        }
    }
    T at(int index){ return dat[index+n-1]; }
    void add(int k,T a){ update(k,at(k)+a); }
    T query(int a,int b) { return query(a,b,0,0,n); }
    T query(int a,int b,int k,int l,int r) {
        if(r<=a or b<=l) return id_;
        if(a<=l and r<=b) return dat[k];
        int m=(l+r)/2;
        return op(query(a,b,k*2+1,l,m),query(a,b,k*2+2,m,r));
    }
};

template<i64 p> class Fp{
    public:
    i64 x;
    Fp():x(0){}
    Fp(i64 x_):x((x_%p+p)%p){}
    Fp operator+()const{ return Fp(x); }
    Fp operator-()const{ return Fp(-x); }
    Fp& operator+=(const Fp& y){ x=((x+y.x)%p+p)%p; return *this ;}
    Fp& operator-=(const Fp& y){ return *this+=-y; }
    Fp& operator*=(const Fp& y){ x=x*y.x%p; return *this; }
    Fp& operator/=(const Fp& y){ return *this*=Fp(inverse(y.x)); }
    Fp operator+(const Fp& y)const{ return Fp(x)+=y; }
    Fp operator-(const Fp& y)const{ return Fp(x)-=y; }
    Fp operator*(const Fp& y)const{ return Fp(x)*=y; }
    Fp operator/(const Fp& y)const{ return Fp(x)/=y; }
    bool operator==(const Fp& y)const{ return x==y.x; }
    bool operator!=(const Fp& y)const{ return !(*this==y); }
    i64 extgcd(i64 a,i64 b,i64 &x,i64 &y){
        i64 d=a;
        if(b!=0){
            d=extgcd(b,a%b,y,x);
            y-=(a/b)*x;
        } else {
            x=1; y=0;
        }
        return d;
    }
    i64 inverse(i64 a){
        i64 x,y;
        extgcd(a,p,x,y);
        return (x%p+p)%p;
    }
};
template<i64 p> ostream &operator<<(ostream& os, const Fp<p> &x) { os << x.x; return os; }
template<i64 p> i64 abs(const Fp<p>& x){ return x.x; }

template<class K> class matrix{
    public:
    int m,n;
    vector<vector<K>> a;
    matrix(){
        m=n=2;
        a=vector<vector<K>>(2,vector<K>(2));
        a[0][0]=a[1][1]=1;
    }
    matrix(int m_,int n_):m(m_),n(n_),a(m_,vector<K>(n_)){}
    matrix(const vector<vector<K>> &v):m(v.size()),n((v.size()==0 or v[0].size()==0)?0:v[0].size()),a(v){}
    //matrix(const matrix<K>& other)=default;
    //~matrix()=default;

    vector<K>& operator[](int i){ assert(0<=i); assert(i<m); return a[i]; }
    matrix<K> operator+()const{ return *this; }
    matrix<K> operator-()const{ return K(-1)**this; }
    K at(int i,int j)const{ return a[i][j]; }
    
    matrix<K>& operator=(const matrix<K> &other)=default;
    matrix<K>& operator+=(const matrix<K> &other){ assert(m==other.m); assert(n==other.n); for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]+=other[i][j]; return *this; }
    matrix<K>& operator-=(const matrix<K> &other){ return (*this)+=-other; }
    matrix<K>& operator*=(const matrix<K> &other){
        assert(n==other.m);
        vector<vector<K>> b(m,vector<K>(other.n));
        for(int i=0; i<m; ++i) for(int j=0; j<other.n; ++j) for(int k=0; k<n; ++k) b[i][j]+=(*this)[i][k]*other.at(k,j);
        a=b;
        return *this;
    } 
    matrix<K>& operator/=(const K& k){ assert(k!=K(0)); for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]/=k; return *this; }
    matrix<K>& operator%=(const K& k){ assert(k!=K(0)); for(int i=0; k<m; ++i) for(int j=0; j<n; ++j) (*this)[i][j]=((*this)[i][j]+k)%k; return *this; }
    matrix<K> operator+(const matrix<K>& other)const{ return matrix<K>(*this)+=other; }
    matrix<K> operator-(const matrix<K>& other)const{ return matrix<K>(*this)-=other; }
    matrix<K> operator*(const matrix<K>& other)const{ return matrix<K>(*this)*=other; }
    matrix<K> operator/(const K& k)const{ return matrix(*this)/=k; }
    matrix<K> operator%(const K& k)const{ return matrix(*this)%=k; }
    
    bool operator==(const matrix<K> &other)const{
        if(m!=other.m or n!=other.n) return false;
        for(int i=0; i<m; ++i) for(int j=0; j<n; ++j) if((*this)[i][j]!=other[i][j]) return false;
        return true;
    }
    bool operator!=(const matrix<K> &other)const{ return !((*this)==other); }

    static matrix<K> E(int m){
        assert(0<=m);
        matrix<K> E_(m,m);
        for(int i=0; i<m; ++i) E_[i][i]=K(1);
        return E_;
    }

    static matrix<K> e(int m,int i){
        assert(0<=i);
        assert(i<m);
        matrix<K> e_;
        e_[i][0]=K(1);
        return e_;
    }
};

template<class K> matrix<K> operator*(const K& k,const matrix<K> &x){
    matrix<K> res(x);
    for(int i=0; i<x.m; ++i) for(int j=0; j<x.n; ++j) res[i][j]*=k;
    return res;
}

template<class K> K tr(const matrix<K>& x){
    assert(x.m==x.n);
    K res(0);
    for(int i=0; i<x.m; ++i) res+=x.at(i,i);
    return res;
}

const i64 mod=1000000007;
using mat=matrix<Fp<mod>>;


mat mul(mat a,mat b){
    mat res(2,2);
    rep(i,0,2) rep(j,0,2) rep(k,0,2) res[i][j]+=a[i][k]*b[k][j];
    return res;
}

void solve(){
    int n;
    cin >> n;

    vector<vector<int>> tree(n);
    vector<pair<int,int>> edges;
    rep(i,0,n-1){
        int a,b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
        edges.push_back(make_pair(a,b));
    }

    vector<int> par(n),dep(n);
    function<void(int,int,int)> dfs=[&](int u,int p,int d){
        par[u]=p;
        dep[u]=d;
        for(int v:tree[u]){
            if(v==p) continue;
            dfs(v,u,d+1);
        }
    };
    dfs(0,-1,0);

    rep(i,0,n-1) if(dep[edges[i].first]>dep[edges[i].second]) swap(dep[edges[i].first],dep[edges[i].second]);
    
    using seg_mat=segtree<mat,mul>;
    HeavyLightDecomposer<seg_mat,vector<seg_mat>> hld(tree,0);
    vector<mat> connections(n,mat::E(2));
    rep(i,0,hld.segments.size()){
        hld.segments[i].init(hld.paths[i].size()-1, mat::E(2), mat::E(2));
    }

    int q;
    cin >> q;
    rep(i,0,q){
        char t;
        cin >> t;
        if(t=='x'){
            int i;
            i64 x00,x01,x10,x11;
            cin >> i >> x00 >> x01 >> x10 >> x11;
            int a=edges[i].first,b=edges[i].second;
            mat tmp(2,2);
            tmp[0][0]=x00;
            tmp[0][1]=x01;
            tmp[1][0]=x10;
            tmp[1][1]=x11;
            if(hld.path_id[a]==hld.path_id[b]){
                hld.segments[hld.path_id[a]].update(hld.local_index[b],tmp);
            }else{
                connections[b]=tmp;
            }
        }else{
            int i,j;
            cin >> i >> j;
            mat ans;
            while(true){
                int pathj=hld.path_id[j];
                if(hld.path_id[i]==hld.path_id[j]){
                    int l=hld.local_index[i],r=hld.local_index[j];
                    ans=hld.segments[pathj].query(l,r)*ans;
                    break;
                }
                ans=hld.segments[pathj].query(0,hld.local_index[j])*ans;
                ans=connections[hld.first[j]]*ans;
                j=hld.go_up(j);
            }
            cout << ans[0][0] << " " << ans[0][1] << " " << ans[1][0] << " " << ans[1][1] << endl;
        }
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}
yukicoder

結果

テストケース

ソースコード
