結果

問題 No.900 aδδitivee
ユーザー Navier_Boltzmann
提出日時 2024-01-07 16:03:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 365 ms / 2,000 ms
コード長 5,783 bytes
コンパイル時間 9,642 ms
コンパイル使用メモリ 354,136 KB
実行使用メモリ 26,400 KB
最終ジャッジ日時 2024-09-27 19:25:58
合計ジャッジ時間 16,501 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k))
#define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k))
#define ll long long
#define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> map<T,int> Counter(vector<T> X){map<T,int> C;for(auto x:X){C[x]++;}; return C;}
struct HLD{
int N;
vector<vector<int>> e;
vector<int> par;
vector<int> sub;
vector<int> dist;
vector<int> head;
vector<int> depth;
vector<int> ID;
vector<int> HEAD;
vector<int> PAR;
vector<int> DEPTH;
vector<int> SUB;
HLD(vector<vector<int>> &_e, int root = 0){
e = _e;
N = (int)(e.size());
par = vector<int> (N,-1);
sub = vector<int> (N,-1);
dist = vector<int> (N,-1);
head = vector<int> (N,-1);
depth = vector<int> (N,-1);
ID = vector<int> (N,-1);
HEAD = vector<int> (N,-1);
PAR = vector<int> (N,-1);
DEPTH = vector<int> (N,-1);
SUB = vector<int> (N,-1);
dist[root] = 0;
deque<int> v;
v.emplace_back(root);
int x;
while(!v.empty()){
x = v.front();v.pop_front();
for (auto ix:e[x]){
if(dist[ix]!=-1) continue;
dist[ix] = dist[x] + 1;
v.emplace_back(ix);
}
}
vector<pair<int,int>> H(N);
for(int i=0;i<N;i++){
H[i] = {-dist[i],i};
}
sort(H.begin(),H.end());
int tmp;
for(auto [h,i]:H){
tmp = 1;
for (auto ix:e[i]){
if(sub[ix]==-1) par[i] = ix;
else tmp += sub[ix];
}
sub[i] = tmp;
}
ID[root] = 0;
vector<bool> visited(N,false);
HEAD[0] = 0;
head[root] = 0;
depth[root] = 0;
DEPTH[0] = 0;
int cnt = 0;
v.emplace_back(root);
SUB[0] = N;
vector<pair<int,int>> h;
int flg = 0;
int n;
while(!v.empty()){
x = v.front();v.pop_front();
visited[x] = true;
ID[x] = cnt;
cnt ++;
n = (int)e[x].size();
h.resize(n);
for(int i=0;i<n;i++){
h[i] = {sub[e[x][i]],e[x][i]};
}
sort(h.begin(),h.end());
flg = 0;
if(x==root){
flg = -1;
}
for(auto [_,ix]:h){
flg ++;
if(visited[ix]) continue;
v.emplace_front(ix);
if(flg==n-1){
head[ix] = head[x];
depth[ix] = depth[x];
}
else{
head[ix] = ix;
depth[ix] = depth[x] + 1;
}
}
}
for(int i=0;i<N;i++){
if(par[i]==-1){
PAR[ID[i]] == -1;
}
else{
PAR[ID[i]] = ID[par[i]];
}
HEAD[ID[i]] = ID[head[i]];
DEPTH[ID[i]] = depth[i];
SUB[ID[i]] = sub[i];
}
}
vector<pair<int,int>> path_query(int l, int r){
int L = ID[l];
int R = ID[r];
pair<int,int> tmp;
vector<pair<int,int>> res;
if(DEPTH[L]<DEPTH[R]){
L = ID[r];
R = ID[l];
}
while(DEPTH[L]!=DEPTH[R]){
tmp = {HEAD[L],L+1};
res.emplace_back(tmp);
L = PAR[HEAD[L]];
}
while (HEAD[L]!=HEAD[R]){
tmp = {HEAD[L],L+1};
res.emplace_back(tmp);
tmp = {HEAD[R],R+1};
res.emplace_back(tmp);
L = PAR[HEAD[L]];
R = PAR[HEAD[R]];
}
tmp = {min(L,R),max(L,R)+1};
res.emplace_back(tmp);
return res;
}
pair<int,int> sub_query(int k){
int K = ID[k];
return {K,K+SUB[K]};
}
};
array<ll,2> ope(array<ll,2> x,array<ll,2> y){
array<ll,2> z;
z[0] = x[0]+y[0];
z[1] = x[1]+y[1];
return z;
}
array<ll,2> e_(){
array<ll,2> z={0};
return z;
}
array<ll,2> mapping(ll f, array<ll,2> x){
array<ll,2> z;
z[0] = x[0]+f*x[1];
z[1] = x[1];
return z;
}
ll composition(ll f,ll g){
return f+g;
}
ll id_(){
return 0;
}
int main(){
int N;
cin >> N;
vector<vector<int>> e(N);
vector<ll> W(N);
int u,v;
ll w;
rep(_,0,N-1,1){
cin >> u >> v >> w;
e[u].emplace_back(v);
e[v].emplace_back(u);
W[v] = w;
}
int Q;
cin >> Q;
HLD hld(e);
vector<int> id = hld.ID;
vector<array<ll,2>> B(N,array<ll,2> {0});
rep(i,0,N,1){
B[id[i]][0] = W[i];
B[id[i]][1] = 1;
}
lazy_segtree<array<ll,2>,ope,e_,ll,mapping,composition,id_> T(B);
int flg,l,r,b,a;
ll x,tmp;
rep(_,0,Q,1){
cin >> flg;
if(flg==1){
cin >> a >> x;
auto [l,r] = hld.sub_query(a);
T.apply(l+1,r,x);
}
else{
cin >> b;
tmp = 0;
for(auto lr:hld.path_query(0,b)){
l = lr.first;
r = lr.second;
tmp += T.prod(l,r)[0];
}
cout << tmp << endl;
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0