結果

問題 No.235 めぐるはめぐる (5)
ユーザー okaduki
提出日時 2017-11-05 22:57:42
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,026 ms / 10,000 ms
コード長 6,551 bytes
コンパイル時間 2,262 ms
コンパイル使用メモリ 184,084 KB
実行使用メモリ 50,788 KB
最終ジャッジ日時 2024-11-24 02:57:54
合計ジャッジ時間 8,031 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;
#define ALL(a) begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
if(x > y) x = y;
}
const double EPS = 1e-10;
const double PI = acos(-1.0);
const LL MOD = 1000000007;
struct Edge{
int to, cost;
Edge(int t, int c = 0): to(t), cost(c)
{}
bool operator>(const Edge& rhs) const{
return cost > rhs.cost;
}
bool operator<(const Edge& rhs) const{
return cost < rhs.cost;
}
};
using Graph = vector<vector<Edge>>;
void add_edge(Graph& graph, int u, int v, int cost = 0){
graph[u].push_back(Edge(v,cost));
graph[v].push_back(Edge(u,cost));
}
class LazySegT{
private:
int NN;
struct Node{
LL dat;
LL lazy;
LL S;
};
vector<Node> segT;
public:
LazySegT(int n, VL& x0, VL& s0){
NN = 1;
while(NN < n) NN <<= 1;
segT.resize(NN*2);
for(int i=0;i<n;++i){
segT[NN-1+i].dat = x0[i];
segT[NN-1+i].S = s0[i];
segT[NN-1+i].lazy = 0;
}
for(int i=NN-2;i>=0;--i){
segT[i].dat = (segT[i*2+1].dat + segT[i*2+2].dat) % MOD;
segT[i].S = (segT[i*2+1].S + segT[i*2+2].S) % MOD;
segT[i].lazy = 0;
}
}
void eval(int k, int l, int r){
if(segT[k].lazy == 0) return;
(segT[k].dat += segT[k].lazy * segT[k].S % MOD) %= MOD;
if(k < NN-1){ // not leaf
(segT[2*k+1].lazy += segT[k].lazy) %= MOD;
(segT[2*k+2].lazy += segT[k].lazy) %= MOD;
}
segT[k].lazy = 0;
}
void update(int a, int b, LL c, int k, int l, int r){
eval(k,l,r);
if(r <= a || b <= l) return;
if(a <= l && r <= b){
(segT[k].lazy += c) %= MOD;
eval(k,l,r);
}
else{
update(a, b, c, k*2+1, l, (l+r)/2);
update(a, b, c, k*2+2, (l+r)/2, r);
segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;
}
}
// dat[idx] += c, a <= idx < b
void update(int a, int b, LL c){
update(a, b, c, 0, 0, NN);
}
LL query(int a, int b, int k, int l, int r){
eval(k,l,r);
if(r <= a || b <= l) return 0;
if(a <= l && r <= b) return segT[k].dat;
else{
LL vl = query(a, b, k*2+1, l, (l+r)/2);
LL vr = query(a, b, k*2+2, (l+r)/2, r);
segT[k].dat = (segT[k*2+1].dat + segT[k*2+2].dat) % MOD;
return (vl+vr) % MOD;
}
}
LL query(int a, int b){
return query(a, b, 0, 0, NN);
}
};
/**
* HL
*
* O(log n)
* HeavyLight
* HeavySegment Tree
*/
struct HL{
int N;
VI depth;
VI par;
VI sz;
//!
VI xs;
//! Heavyid
VI heavy_id;
//!
VI heavy_nth;
//! heavys[id] := {idHeavy}
VVI heavys;
//! Heavyheavy_id
VI heavy_par;
//! heavy
int H;
HL(const Graph& G, int root = 0, const VI& xs_ = {}){
N = SZ(G);
depth.assign(N, 0);
par.assign(N, -1);
sz.assign(N, 1);
if(!xs_.empty())
xs = xs_;
else
xs.assign(N, 0);
heavy_id.assign(N, -1);
heavy_nth.assign(N, 0);
heavys.assign(N, {});
heavy_par.assign(N, -1);
function<void(int,int)> init = [&](int u, int p){
par[u] = p;
for(auto& e: G[u]){
if(e.to == p) continue;
depth[e.to] = depth[u] + 1;
init(e.to, u);
sz[u] += sz[e.to];
if(xs_.empty())
xs[e.to] = e.cost;
}
};
depth[root] = 0;
init(root, -1);
H = 1;
function<void(int,int)> calcHL = [&](int u, int p){
heavy_nth[u] = SZ(heavys[heavy_id[u]]);
heavys[heavy_id[u]].PB(u);
int max_u = -1;
for(auto& e: G[u]){
if(e.to == p) continue;
if(max_u < 0 || sz[max_u] < sz[e.to])
max_u = e.to;
}
if(max_u < 0) return;
heavy_id[max_u] = heavy_id[u];
calcHL(max_u, u);
for(auto& e: G[u]){
if(e.to == p || e.to == max_u) continue;
heavy_id[e.to] = H++;
calcHL(e.to, u);
heavy_par[heavy_id[e.to]] = heavy_id[u];
}
};
heavy_id[root] = 0;
calcHL(root, -1);
}
int LCA(int u, int v){
while(true){
if(heavy_id[u] == heavy_id[v])
return (depth[u] <= depth[v]? u: v);
int ru = heavys[heavy_id[u]][0];
int rv = heavys[heavy_id[v]][0];
if(depth[ru] < depth[rv])
v = par[rv];
else
u = par[ru];
}
}
vector<LazySegT> segs;
void initSegs(VI& cs){
REP(i,H){
int n = SZ(heavys[i]);
VL x0(n), s0(n);
REP(k,n){
int id = heavys[i][k];
x0[k] = xs[id];
s0[k] = cs[id];
}
segs.EB(n, x0, s0);
}
}
// Require: p is ancestor of u
void add(int p, int u, LL x){
while(heavy_id[p] != heavy_id[u]){
int hid = heavy_id[u];
segs[hid].update(0, heavy_nth[u]+1, x);
u = par[heavys[hid][0]];
}
int hid = heavy_id[u];
segs[hid].update(heavy_nth[p], heavy_nth[u]+1, x);
}
// Require: p is ancestor of u
LL query(int p, int u){
LL res = 0;
while(heavy_id[p] != heavy_id[u]){
int hid = heavy_id[u];
(res += segs[hid].query(0, heavy_nth[u]+1)) %= MOD;
u = par[heavys[hid][0]];
}
int hid = heavy_id[u];
(res += segs[hid].query(heavy_nth[p], heavy_nth[u]+1)) %= MOD;
return res;
}
};
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int N;
cin >> N;
VI xs(N), cs(N);
REP(i,N) cin >> xs[i];
REP(i,N) cin >> cs[i];
Graph G(N);
REP(i,N-1){
int a, b;
cin >> a >> b;
--a;
--b;
add_edge(G, a, b);
}
auto hl = HL(G, 0, xs);
hl.initSegs(cs);
int Q;
cin >> Q;
while(Q--){
int T;
int x, y, z;
cin >> T >> x >> y;
--x;
--y;
if(!T){
cin >> z;
int lca = hl.LCA(x, y);
hl.add(lca, x, z);
hl.add(lca, y, z);
hl.add(lca, lca, MOD-z);
}
else{
int lca = hl.LCA(x, y);
cout << (hl.query(lca, x) + hl.query(lca, y) + MOD - hl.query(lca, lca))%MOD << endl;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0