結果
| 問題 | No.900 aδδitivee |
| ユーザー |
 leaf_1415
|
| 提出日時 | 2019-10-04 22:24:10 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 370 ms / 2,000 ms |
| コード長 | 6,001 bytes |
| コンパイル時間 | 1,429 ms |
| コンパイル使用メモリ | 99,440 KB |
| 実行使用メモリ | 42,496 KB |
| 最終ジャッジ日時 | 2024-10-03 07:59:58 |
| 合計ジャッジ時間 | 10,025 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define llint long long
#define inf 1e18
using namespace std;
struct edge{
llint to, cost;
edge(){}
edge(llint a, llint b){
to = a, cost = b;
}
};
typedef pair<int, int> P;
struct HLD{
int V, logV;
vector<P> mp;
map<P, int> mp2;
vector<P> parent;
//subtree of v is [pre_order[v], back_order[v]]
vector<int> pre_order;
vector<int> back_order;
int order;
int global_id, local_id;
vector<int> size, depth;
vector<vector<int> > prev;
HLD(){}
void predfs(vector<int> G[], int v, int p, int d)
{
size[v] = 1, depth[v] = d, prev[v][0] = p;
for(int i = 0; i < G[v].size(); i++){
if(G[v][i] == p) continue;
predfs(G, G[v][i], v, d+1);
size[v] += size[G[v][i]];
}
}
void maindfs(vector<int> G[], int v, int p)
{
mp[v] = make_pair(global_id, local_id);
mp2[make_pair(global_id, local_id)] = v;
pre_order[v] = ++order;
if(G[v].size() == 1 && G[v][0] == p){
back_order[v] = order;
return;
}
vector<P> vec;
for(int i = 0; i < G[v].size(); i++){
if(G[v][i] == p) continue;
vec.push_back(make_pair(size[G[v][i]], G[v][i]));
}
sort(vec.rbegin(), vec.rend());
local_id++;
if(vec.size() >= 1) maindfs(G, vec[0].second, v);
for(int i = 1; i < vec.size(); i++){
parent.push_back(mp[v]);
global_id++, local_id = 0;
maindfs(G, vec[i].second, v);
}
back_order[v] = order;
}
int getLCA(int u, int v){
int x = u, y = v;
if(depth[y] > depth[x]) swap(x, y);
for(int i = logV-1; i >= 0; i--){
if(depth[x] - (1<<i) >= depth[y]) x = prev[x][i];
}
if(x == y) return x;
for(int i = logV-1; i >= 0; i--){
if(prev[x][i] != prev[y][i]){
x = prev[x][i];
y = prev[y][i];
}
}
x = prev[x][0];
return x;
}
void pathcalc(int v, int lca, vector<pair<int, P> > &dest)
{
int gid = mp[v].first, lid = mp[v].second;
int Gid = mp[lca].first, Lid = mp[lca].second;
while(Gid != gid){
dest.push_back(make_pair(gid, make_pair(0, lid)));
int ngid = parent[gid].first, nlid = parent[gid].second;
gid = ngid, lid = nlid;
}
dest.push_back(make_pair(gid, make_pair(Lid, lid)));
}
void init(vector<int> G[], int V) // The tree must be 1-indexed.
{
this->V = V, logV = 0;
for(int t = V; t; t/=2) logV++;
prev.resize(V+1);
for(int i = 0; i <= V; i++) prev[i].resize(logV);
size.resize(V+1), depth.resize(V+1);
predfs(G, 1, 0, 0);
prev[0][0] = 0;
for(int i = 1; i < logV; i++){
for(int j = 1; j <= V; j++){
prev[j][i] = prev[prev[j][i-1]][i-1];
}
}
mp.resize(V+1), mp2.clear();
parent.clear(), parent.push_back(make_pair(-1, -1));
pre_order.resize(V+1), back_order.resize(V+1);
global_id = local_id = 0, order = 0;
maindfs(G, 1, 0);
}
void path(int u, int v, vector<pair<int, P> > &dest)
{
dest.clear();
int lca = getLCA(u, v);
pathcalc(u, lca, dest);
pathcalc(v, lca, dest);
pair<int, P> p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second));
for(int i = 0; i < dest.size(); i++){
if(dest[i] == p){
dest.erase(dest.begin()+i);
return ;
}
}
}
void toOrder(vector<pair<int, P> > &src, vector<P> &dest)
{
dest.clear();
for(int i = 0; i < src.size(); i++){
int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)];
dest.push_back(make_pair(pre_order[u], pre_order[v]));
}
}
};
// range-add, range-min query
struct SegTree{
int size;
vector<llint> seg, delay;
SegTree(){}
SegTree(int size){
this->size = size;
seg.resize(1<<(size+1));
delay.resize(1<<(size+1));
}
void init()
{
for(int i = 0; i < (1<<(size+1)); i++){
seg[i] = 0;
delay[i] = 0;
}
}
void eval(int l, int r, int k)
{
if(delay[k]){
seg[k] += delay[k] * (r-l+1);
if(l < r){
delay[k*2] += delay[k];
delay[k*2+1] += delay[k];
}
delay[k] = 0;
}
}
void update(int i, llint val)
{
i += (1 << size);
seg[i] = val;
while(i > 1){
i /= 2;
seg[i] = (seg[i*2] + seg[i*2+1]);
}
}
void add(int a, int b, int k, int l, int r, llint val)
{
eval(l, r, k);
if(b < l || r < a) return;
if(a <= l && r <= b){
delay[k] += val;
eval(l, r, k);
return;
}
add(a, b, k*2, l, (l+r)/2, val);
add(a, b, k*2+1, (l+r)/2+1, r, val);
seg[k] = (seg[k*2] + seg[k*2+1]);
}
void add(int a, int b, llint val){
if(a > b) return;
add(a, b, 1, 0, (1<<size)-1, val);
}
llint query(int a, int b, int k, int l, int r)
{
eval(l, r, k);
if(b < l || r < a) return 0;
if(a <= l && r <= b) return seg[k];
llint lval = query(a, b, k*2, l, (l+r)/2);
llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
return (lval + rval);
}
llint query(int a, int b)
{
return query(a, b, 1, 0, (1<<size)-1);
}
};
llint n, Q;
vector<int> G[100005];
llint a[100005];
HLD hld;
SegTree seg(17);
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
llint u, v, w;
for(int i = 1; i <= n-1; i++){
cin >> u >> v >> w;
u++, v++;
G[u].push_back(v);
a[v] = w;
}
hld.init(G, n);
//for(int i = 1; i <= n; i++) cout << hld.pre_order[i] << " "; cout << endl;
for(int i = 1; i <= n; i++) seg.add(hld.pre_order[i], hld.pre_order[i], a[i]);
cin >> Q;
llint t, p, x;
for(int q = 0; q < Q; q++){
cin >> t;
if(t == 1){
cin >> p >> x;
p++;
//cout << "! " << hld.pre_order[p] << " " << hld.back_order[p] << endl;
seg.add(hld.pre_order[p], hld.back_order[p], x);
seg.add(hld.pre_order[p], hld.pre_order[p], -x);
}
else{
cin >> p;
p++;
vector<pair<int, P> > tmp;
hld.path(1, p, tmp);
vector<P> vec;
hld.toOrder(tmp, vec);
llint ans = 0;
for(int i = 0; i < vec.size(); i++){
//cout << vec[i].first << " " << vec[i].second << endl;
ans += seg.query(vec[i].first, vec[i].second);
}
cout << ans << "\n";
}
//for(int i = 1; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl;
}
flush(cout);
return 0;
}