結果
問題 | No.900 aδδitivee |
ユーザー |
![]() |
提出日時 | 2024-06-01 09:20:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 446 ms / 2,000 ms |
コード長 | 9,989 bytes |
コンパイル時間 | 6,317 ms |
コンパイル使用メモリ | 291,100 KB |
実行使用メモリ | 42,800 KB |
最終ジャッジ日時 | 2024-12-21 14:21:20 |
合計ジャッジ時間 | 17,449 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#ifdef t9unkubj#include"template.h"//#include"template_no_debug.h"#else#undef _GLIBCXX_DEBUG#pragma GCC optimize("O3")#define dbg(...) 199958using namespace std;#include<bits/stdc++.h>using uint=unsigned;using ll=long long;using ull=unsigned long long;using ld=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;template<class T>using vc=vector<T>;template<class T>using vvc=vc<vc<T>>;template<class T>using vvvc=vvc<vc<T>>;using vi=vc<int>;using vvi=vc<vi>;using vvvi=vc<vvi>;using vl=vc<ll>;using vvl=vc<vl>;using vvvl=vc<vvl>;template<class T>using smpq=priority_queue<T,vector<T>,greater<T>>;template<class T>using bipq=priority_queue<T>;#define rep(i,n) for(ll (i)=0;i<(ll)(n);i++)#define REP(i,j,n) for(ll (i)=(j);i<(ll)(n);i++)#define DREP(i,n,m) for(ll (i)=(n);i>=(m);i--)#define drep(i,n) for(ll i=((n)-1);i>=0;i--)#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define mp make_pair#define mt make_tuple#define pb push_back#define eb emplace_back#define fi first#define se second#define is insert#define bg begin()#define ed end()void scan(int&a) { cin >> a; }void scan(ll&a) { cin >> a; }void scan(string&a) { cin >> a; }void scan(char&a) { cin >> a; }void scan(uint&a) { cin >> a; }void scan(ull&a) { cin >> a; }void scan(bool&a) { cin >> a; }void scan(ld&a){ cin>> a;}template<class T> void scan(vector<T>&a) { for(auto&x:a) scan(x); }void read() {}template<class Head, class... Tail> void read(Head&head, Tail&... tail) { scan(head); read(tail...); }#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; read(__VA_ARGS__);#define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__);#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);#define CHR(...) char __VA_ARGS__; read(__VA_ARGS__);#define DBL(...) double __VA_ARGS__; read(__VA_ARGS__);#define LD(...) ld __VA_ARGS__; read(__VA_ARGS__);#define VC(type, name, ...) vector<type> name(__VA_ARGS__); read(name);#define VVC(type, name, size, ...) vector<vector<type>> name(size, vector<type>(__VA_ARGS__)); read(name);void print(int a) { cout << a; }void print(ll a) { cout << a; }void print(string a) { cout << a; }void print(char a) { cout << a; }void print(uint a) { cout << a; }void print(bool a) { cout << a; }void print(ull a) { cout << a; }void print(ld a){ cout<< a; }template<class T> void print(vector<T>a) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout<<endl;}void PRT() { cout <<endl; return ; }template<class T> void PRT(T a) { print(a); cout <<endl; return; }template<class Head, class... Tail> void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; }template<class T,class F>bool chmin(T &x, F y){if(x>y){x=y;return true;}return false;}template<class T, class F>bool chmax(T &x, F y){if(x<y){x=y;return true;}return false;}void YesNo(bool b){cout<<(b?"Yes":"No")<<endl;}void Yes(){cout<<"Yes"<<endl;}void No(){cout<<"No"<<endl;}template<class T>int popcount(T n){return __builtin_popcount(n);}template<class T>T sum(vc<T>&a){return accumulate(all(a),T(0));}template<class T>T max(vc<T>&a){return *max_element(all(a));}template<class T>T min(vc<T>&a){return *min_element(all(a));}template<class T>void unique(vc<T>&a){a.erase(unique(all(a)),a.end());}vvi readgraph(int n,int m,int off = -1){vvi g(n);rep(i, m){int u,v;cin>>u>>v;u+=off,v+=off;g[u].push_back(v);g[v].push_back(u);}return g;}vvi readtree(int n,int off=-1){return readgraph(n,n-1,off);}template<class T>vc<T> presum(vc<T> &a){vc<T> ret(a.size()+1);rep(i,a.size())ret[i+1]=ret[i]+a[i];return ret;}template<class T, class F>vc<T> &operator+=(vc<T> &a,F b){for (auto&v:a)v += b;return a;}template<class T, class F>vc<T> &operator-=(vc<T>&a,F b){for (auto&v:a)v-=b;return a;}template<class T, class F>vc<T> &operator*=(vc<T>&a,F b){for (auto&v:a)v*=b;return a;}#endifdouble pass_time=0;#include<vector>#include<cassert>#include<algorithm>struct HLD{int n;std::vector<int>depth,head,siz_,par,in,out;std::vector<std::vector<int>>g,c;HLD(int n):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(n),c(n){}HLD(int n,std::vector<std::vector<int>>g):n(n),depth(n),head(n),siz_(n,1),in(n),out(n),g(g),c(n){}void add_edge(int u,int v,bool d=0){g[u].emplace_back(v);if(d)g[v].emplace_back(u);}void init_dfs1(int now,int pre){for(int &x:g[now]){if(x==pre)continue;c[now].emplace_back(x);depth[x]=depth[now]+1;par[x]=now;init_dfs1(x,now);siz_[now]+=siz_[x];}}void init_dfs2(int now,int pre,int&order){in[now]=order++;for(int i=0;i<(int)c[now].size();i++){if(siz_[c[now][0]]<siz_[c[now][i]])std::swap(c[now][0],c[now][i]);}for(int x:c[now]){if(x==c[now][0])head[x]=head[now];else head[x]=x;init_dfs2(x,now,order);}out[now]=order++;}void init(int root=0){//rootからの有向辺にになることに注意par=head=std::vector<int>(n,root);int order{};init_dfs1(root,-1);init_dfs2(root,-1,order);}int lca(int u,int v){//O(logN) u,vのlcaを取得するif(head[u]==head[v])return (depth[u]>depth[v]?v:u);if(depth[head[u]]>depth[head[v]])std::swap(u,v);v=par[head[v]];return lca(u,v);}int f1(int a){//入った時間を返すO(1)return in[a];}int f2(int a){//出た時間を返すO(1)return out[a];}int dis(int u,int v){//uとvの最短距離を求めるO(logN)assert(0<=u&&u<n);assert(0<=v&&v<n);return depth[u]+depth[v]-2*depth[lca(u,v)];}template<class T,class G>void set(int u,T&seg,G x){seg.set(f1(u),x);}vector<pair<int,int>> prod(int u,int v,bool edge){//[u,v]の演算結果を取得する,G>ret T>seg木 O(log^2N)vector<pair<int,int>>resl,resr;while(1){if(in[u]>in[v])swap(u,v),swap(resl,resr);if(head[u]==head[v])break;resr.push_back({in[head[v]],in[v]+1});v=par[head[v]];}resr.push_back({in[u]+edge,in[v]+1});for(auto x:resr)resl.push_back(x);return resl;}};template <class T,T (*op)(T, T),class F,T (*mapping)(T,F),F (*merge)(F, F)>struct lazy_segtree{int n;vector<T>data;vector<F>lazy;int log;T e;F id;lazy_segtree(int n1,T e,F id):n(n1),e(e),id(id){int n_=1;log=0;while(n_<=n)n_*=2,log++;data=vector<T>(n_*2,e);lazy=vector<F>(n_,id);n=n_;for(int i=n_-1;i>0;i--)update(i);}void update(int k){data[k]=op(data[k*2],data[k*2+1]);}void apply(int k,F x){//data[k]=mapping(data[k],x);if(k<n){lazy[k]=merge(lazy[k],x);if(lazy[k]==id)return;//segment tree beats! if(data[k].fail)push(k),update(k);}}void push(int k){//上から遅延素を伝播させるapply(k*2,lazy[k]);apply(k*2+1,lazy[k]);lazy[k]=id;}void set(int p,T x){p+=n;for(int i=log;i>=1;i--){push(p>>i);}data[p]=x;for(int i=1;i<=log;i++){update(p>>i);}}void apply(int l,int r,F x){if(l==r)return;l+=n,r+=n;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}int l2{l},r2{r};while(l<r){if(l&1)apply(l++,x);if(r&1)apply(--r,x);l>>=1,r>>=1;}l=l2,r=r2;for(int i=1;i<=log;i++){if(((l>>i)<<i)!=l)update(l>>i);if(((r>>i)<<i)!=r)update((r-1)>>i);}}T prod(int l,int r){l+=n,r+=n;for(int i=log;i>=1;i--){if(((l>>i)<<i)!=l)push(l>>i);if(((r>>i)<<i)!=r)push((r-1)>>i);}T sml=e,smr=e;while(l<r){if(l&1)sml=op(sml,data[l++]);if(r&1)smr=op(data[--r],smr);l>>=1,r>>=1;}return op(sml,smr);}T get(int p){p+=n;for(int i=log;i>=1;i--)push(p>>i);return data[p];}};pll op(pll a,pll b){return mp(a.fi+b.fi,a.se+b.se);}pll op2(pll a,ll b){return mp(a.fi+a.se*b,a.se);}ll op3(ll a,ll b){return a+b;}void solve(){INT(n);vvc<pll>g(n);rep(i,n-1){LL(u,v,w);g[u].pb({v,w});g[v].pb({u,w});}vvi ng(n);vi c(n);auto dfs=[&](auto&dfs,int u,int v)->void{for(auto [x,w]:g[u]){if(x==v)continue;c[x]=w;ng[u].pb(x);dfs(dfs,x,u);}};dfs(dfs,0,-1);HLD hld(n,ng);hld.init();lazy_segtree<pll,op,ll,op2,op3>seg(n+n,mp(0ll,0ll),0);rep(i,n){seg.set(hld.f1(i),mp(c[i],1ll));}INT(q);while(q--){INT(t);if(t==1){LL(a,x);seg.apply(hld.f1(a)+1,hld.f2(a),x);}else{INT(b);pll res{};for(auto [x,y]:hld.prod(0,b,1)){dbg(x,y);res=op(res,seg.prod(x,y));}PRT(res.fi);}}}signed main(){#ifdef t9unkubjfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endifcin.tie(0)->sync_with_stdio(0);pass_time=clock();int t=1;//cin>>t;while(t--)solve();pass_time=clock()-pass_time;dbg(pass_time/CLOCKS_PER_SEC);}