結果
問題 | No.2676 A Tourist |
ユーザー |
![]() |
提出日時 | 2024-10-02 02:14:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,505 ms / 5,000 ms |
コード長 | 12,115 bytes |
コンパイル時間 | 5,084 ms |
コンパイル使用メモリ | 289,408 KB |
実行使用メモリ | 79,492 KB |
最終ジャッジ日時 | 2024-10-02 02:15:18 |
合計ジャッジ時間 | 34,630 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#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>std::ostream& operator<<(std::ostream& os, __int128 num) {if (num == 0) {os << "0";return os;}if (num < 0) {os << "-";num = -num;}std::string result;while (num > 0) {result += '0' + static_cast<int>(num % 10);num /= 10;}std::reverse(result.begin(), result.end());os << result;return os;}std::istream& operator>>(std::istream& is, __int128& num) {std::string input;is >> input;bool negative = false;num = 0;if (input[0] == '-') {negative = true;input = input.substr(1);}for (char c : input) {if (c >= '0' && c <= '9') {num = num * 10 + (c - '0');} else {is.setstate(std::ios::failbit);return is;}}if (negative) {num = -num;}return is;}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 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(double 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_popcountll(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;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];}};using bint=ll;bint op(bint a,bint b){return a+b;}#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){}int inited=0;void add_edge(int u,int v,bool d){g[u].push_back(v);if(d)g[v].push_back(u);}void init_dfs1(int now,int pre){for(int &x:g[now]){if(x==pre)continue;c[now].push_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);}template<class G,class T>G prod(int u,int v,bool edge,T&seg){//[u,v]の演算結果を取得する,G>ret T>seg木 O(log^2N)G sml=seg.e,smr=seg.e;while(1){if(in[u]>in[v])swap(u,v),swap(sml,smr);if(head[u]==head[v])break;smr=op(smr,seg.prod(in[head[v]],in[v]+1));v=par[head[v]];}return op(sml,op(smr,seg.prod(in[u]+edge,in[v]+1)));}vector<vector<int>>db;void la_init(){int log=0;while((1<<log)<n)log++;db.resize(log,vector<int>(n));db[0]=par;for(int i=1;i<log;i++){for(int j=0;j<n;j++){int nxt=db[i-1][j];if(nxt==-1)db[i][j]=-1;else{db[i][j]=db[i-1][nxt];}}}}int la(int x,int p){int now=0;while(p){if(p&1)x=db[now][x];p>>=1;now++;if(x==-1)return -1;}return x;}};using L=lazy_segtree<bint,op,bint,op,op>;void solve(){INT(n,q);VC(int,a,n);constexpr int B=300;HLD hld(n);vvi g(n);rep(i,n-1){INT(u,v);hld.add_edge(--u,--v,1);g[u].pb(v);g[v].pb(u);}hld.init();L other(n*2,0,0);L my(n*2,0,0);rep(i,n)for(auto&x:g[i])other.set(hld.f1(x),other.get(hld.f1(x))+a[i]);rep(i,n)my.set(hld.f1(i),a[i]);vi bigs;vi is(n);vl lazy(n);rep(i,n){if(g[i].size()>=B)bigs.pb(i),is[i]=1,dbg(i);}rep(i,q){LL(t,u,x);--u;if(t==0){if(is[u]){lazy[u]+=x;}else{for(auto&to:g[u]){other.set(hld.f1(to),other.get(hld.f1(to))+x);}my.set(hld.f1(u),my.get(hld.f1(u))+x);}}else{dbg(g[x][0],g[u][0]);--x;bint res=hld.prod<bint,L>(u,x,0,other)-hld.prod<bint,L>(u,x,0,my);res+=(my.get(hld.f1(u))+my.get(hld.f1(x)));int lc=hld.lca(u,x);for(auto&to:bigs){if(hld.depth[lc]>hld.depth[to]){if(hld.par[lc]==to){res+=lazy[to];}}else {if(hld.lca(lc,to)!=lc)continue;int dist=min(hld.dis(to,hld.lca(u,to)),hld.dis(to,hld.lca(x,to)));if(dist<=1){res+=lazy[to];}}}cout<<res<<endl;}}}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);}