結果

問題 No.235 めぐるはめぐる (5)
ユーザー koprickykopricky
提出日時 2018-06-04 16:56:10
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 8,441 bytes
コンパイル時間 3,908 ms
コンパイル使用メモリ 186,544 KB
実行使用メモリ 75,936 KB
最終ジャッジ日時 2023-09-12 22:12:19
合計ジャッジ時間 9,804 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 200005;

inline int add(int x,int y)
{
    return (x + y)%MOD;
}

inline int sub(int x,int y)
{
    return (x+MOD-y)%MOD;
}

inline int mul(int x,int y)
{
    return (ll)x*y%MOD;
}

int s[MAX_N],c[MAX_N];

template<typename T> class RootedCentroidDecomposition
{
public:
    struct edge {
        int to; T cost;
    };
    int V, LOGV, CentroidRoot;
    vector<vector<edge> > G;
    vector<vector<int> > TreeID, centroid, parent;
    vector<vector<T> > height;
    vector<bool> used;
    vector<int> depth, stsize;
    vector<T> constant, init, gap, plus;
    void FirstDFS(int u, int par, int dep, T val, T val2){
        init[u] = val;
        constant[u] = val2, parent[0][u] = par;
        depth[u] = dep, stsize[u] = 1;
        for(auto& e : G[u]){
            if(!used[e.to] && e.to != par){
                e.cost = c[e.to-1];
                FirstDFS(e.to, u, dep + 1, add(val, e.cost), add(val2, s[e.to-1]));
                stsize[u] += stsize[e.to];
            }
        }
    }
    void CalcSize(int u, int par){
        stsize[u] = 1;
        for(auto& e : G[u]){
            if(!used[e.to] && e.to != par){
                CalcSize(e.to, u);
                stsize[u] += stsize[e.to];
            }
        }
    }
    void CalcRootHeight(int u, int par, const int cent, const int dep, T val){
        TreeID[dep][u] = 0, height[dep][u] = val;
        for(auto& e : G[u]){
            if(!used[e.to] && e.to != par){
                if(TreeID[dep][e.to] == 0){
                    CalcRootHeight(e.to, u, cent, dep, add(val, e.cost));
                }else{
                    CalcRootHeight(e.to, u, cent, dep, val);
                }
            }
        }
    }
    void CalcHeight(int u, int par, const int ID, const int dep, const T val){
        TreeID[dep][u] = ID, height[dep][u] = val;
        for(auto& e : G[u]){
            if(!used[e.to] && e.to != par){
                CalcHeight(e.to, u, ID, dep, val);
            }
        }
    }
    void RecBuild(int r, int par, int ID, int dep){
        if(par < 0){
            FirstDFS(r, -1, 0, 0, 0);
        }else{
            CalcSize(r, -1);
        }
        int sz = stsize[r], p = -1;
        bool ok = false;
        int cent = r;
        while(!ok){
            ok = true;
            for(auto& e : G[cent]){
                if(!used[e.to] && e.to != p && 2*stsize[e.to] > sz){
                    p = cent, cent = e.to, ok = false;
                    break;
                }
            }
        }
        if(par >= 0){
            centroid[par][ID] = cent;
        }else{
            CentroidRoot = cent;
        }
        // cout << r << " " << cent << endl;
        int nwnode = cent;
        while(nwnode != r){
            TreeID[dep][nwnode] = 0;
            nwnode = parent[0][nwnode];
        }
        used[cent] = true;
        T diff = ID?sub(init[r], init[parent[0][r]]):0;
        height[dep][cent] = add(sub(init[cent], init[r]), diff);
        int childID = 1;
        for(auto& e : G[cent]){
            if(!used[e.to]){
                if(e.to == parent[0][cent]){
                    CalcRootHeight(r, -1, cent, dep, diff);
                }else{
                    CalcHeight(e.to, -1, childID++, dep, height[dep][cent]);
                }
            }
        }
        centroid[cent].resize(childID, -1);
        childID = 1;
        // show("START");
        for(auto& e : G[cent]){
            // cout << cent << " " << e.to << " " << e.cost << endl;
            if(!used[e.to]){
                if(e.to == parent[0][cent]){
                    // show(r);
                    RecBuild(r, cent, 0, dep+1);
                }else{
                    RecBuild(e.to, cent, childID++, dep+1);
                }
            }
        }
    }
    int LCA(int u, int v){
        if(depth[u] > depth[v]) swap(u,v);
        for(int i = 0; i < LOGV; i++){
            if((depth[v] - depth[u]) & (1 << i)){
                v = parent[i][v];
            }
        }
        if(u == v) return u;
        for(int i = LOGV - 1; i >= 0; i--){
            if(parent[i][u] != parent[i][v]){
                u = parent[i][u], v = parent[i][v];
            }
        }
        return parent[0][u];
    }
    void Range(const int u, int cent, int dep, const T val){
        gap[cent] = add(gap[cent], mul(val, height[dep][u]));
        int NextID = TreeID[dep][u];
        if(NextID < 0) return;
        if(NextID != 0){
            plus[cent] = add(plus[cent], val);
        }
        if(u != cent){
            Range(u, centroid[cent][NextID], dep + 1, val);
        }
    }
    T Query(const int u, int dep, int cent){
        if(u == cent) return add(gap[cent], constant[u]);
        int NextID = TreeID[dep][u];
        if(NextID < 0){
            return constant[u];
        }
        if(NextID == 0){
            return add(mul(plus[cent], height[dep][u]), Query(u, dep + 1, centroid[cent][NextID]));
        }else{
            return add(gap[cent], Query(u, dep + 1, centroid[cent][NextID]));
        }
    }
public:
    RootedCentroidDecomposition(const int node_size) : V(node_size), LOGV(ceil(log2(V))), CentroidRoot(-1),
        G(V), TreeID(LOGV, vector<int>(V, -1)), centroid(V), parent(LOGV, vector<int>(V, -1)),
        height(LOGV, vector<T>(V, 0)), used(V, false), depth(V, 0), stsize(V, 0), constant(V, 0),
        init(V, 0), gap(V, 0), plus(V, 0){}
    void add_edge(const int u, const int v, const T cost){
        G[u].push_back((edge){v, cost}),G[v].push_back((edge){u, cost});
    }
    void build(){
        RecBuild(0, -1, 0, 0);
        for(int i = 0; i < LOGV - 1; i++){
            for(int j = 0; j < V; j++){
                if(parent[i][j] >= 0){
                    parent[i+1][j] = parent[i][parent[i][j]];
                }
            }
        }
    }
    void range(int u, int v, const T val){
        if(u == v) return;
        int lca = LCA(u, v);
        Range(u, CentroidRoot, 0, val), Range(v, CentroidRoot, 0, val);
        Range(lca, CentroidRoot, 0, MOD-val), Range(parent[0][lca], CentroidRoot, 0, MOD-val);
    }
    T query(int u, int v){
        if(u == v) return 0;
        T r1 = Query(u, 0, CentroidRoot), r2 = Query(v, 0, CentroidRoot);
        int lca = LCA(u, v);
        T r3 = Query(lca, 0, CentroidRoot), r4 = Query(parent[0][lca], 0, CentroidRoot);
        // cout << r1 << " " << r2 << " " << r3 << " " << r4 << "\n";
        return  r1 + r2 - r3 - r4;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    rep(i,n){
        cin >> s[i];
    }
    rep(i,n){
        cin >> c[i];
    }
    RootedCentroidDecomposition<int> rcd(n+1);
    rcd.add_edge(0, 1, 0);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        rcd.add_edge(a, b, 0);
    }
    rcd.build();
    int q;
    cin >> q;
    rep(i,q){
        int a;
        cin >> a;
        if(a == 0){
            int b,c,d;
            cin >> b >> c >> d;
            rcd.range(b, c, d);
        }else{
            int b,c;
            cin >> b >> c;
            cout << rcd.query(b, c) << "\n";
        }
    }
    return 0;
}
0