結果
| 問題 | No.2676 A Tourist |
| ユーザー |
 woodywoody
|
| 提出日時 | 2024-03-16 00:19:23 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 805 ms / 5,000 ms |
| コード長 | 10,643 bytes |
| コンパイル時間 | 4,635 ms |
| コンパイル使用メモリ | 250,228 KB |
| 実行使用メモリ | 55,916 KB |
| 最終ジャッジ日時 | 2024-09-30 03:35:25 |
| 合計ジャッジ時間 | 18,038 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
コンパイルメッセージ
main.cpp: In member function 'void HeavyLightDecomposition::path_query(int, int, bool, const F&)':
main.cpp:173:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
173 | for (auto &&[a, b] : _ascend(u, l)){
| ^
main.cpp:178:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
178 | for (auto &&[a, b] : _descend(l, v)){
| ^
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,b) for(int i=0;i<b;i++)#define rrep(i,b) for(int i=b-1;i>=0;i--)#define rep1(i,b) for(int i=1;i<b;i++)#define repx(i,x,b) for(int i=x;i<b;i++)#define rrepx(i,x,b) for(int i=b-1;i>=x;i--)#define fore(i,a) for(auto& i:a)#define rng(x) (x).begin(), (x).end()#define rrng(x) (x).rbegin(), (x).rend()#define sz(x) ((int)(x).size())#define pb push_back#define fi first#define se second#define pcnt __builtin_popcountllusing namespace std;using namespace atcoder;using ll = long long;using ld = long double;template<typename T> using mpq = priority_queue<T, vector<T>, greater<T>>;template<typename T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<typename T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }template<typename T> ll sumv(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}bool yn(bool a) { if(a) {cout << "Yes" << endl; return true;} else {cout << "No" << endl; return false;}}#define retval(x) {cout << #x << endl; return;}#define cout2(x,y) cout << x << " " << y << endl;#define coutp(p) cout << p.fi << " " << p.se << endl;#define out cout << ans << endl;#define outd cout << fixed << setprecision(20) << ans << endl;#define outm cout << ans.val() << endl;#define outv fore(yans , ans) cout << yans << "\n";#define outdv fore(yans , ans) cout << yans.val() << "\n";#define assertmle(x) if (!(x)) {vi v(3e8);}#define asserttle(x) if (!(x)) {while(1){}}#define coutv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}#define coutv2(v) fore(vy , v) cout << vy << "\n";#define coutvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define coutvm2(v) fore(vy , v) cout << vy.val() << "\n";using pll = pair<ll,ll>;using pil = pair<int,ll>;using pli = pair<ll,int>;using pii = pair<int,int>;using pdd = pair<ld,ld>;using vi = vector<int>;using vd = vector<ld>;using vl = vector<ll>;using vs = vector<string>;using vb = vector<bool>;using vpii = vector<pii>;using vpli = vector<pli>;using vpll = vector<pll>;using vpil = vector<pil>;using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvs = vector<vector<string>>;using vvb = vector<vector<bool>>;using vvpii = vector<vector<pii>>;using vvpli = vector<vector<pli>>;using vvpll = vector<vpll>;using vvpil = vector<vpil>;using mint = modint998244353;//using mint = modint1000000007;//using mint = dynamic_modint<0>;using vm = vector<mint>;using vvm = vector<vector<mint>>;vector<int> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};ll gcd(ll a, ll b) { return a?gcd(b%a,a):b;}ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}#define yes {cout <<"Yes"<<endl;}#define no {cout <<"No"<<endl;}const double eps = 1e-10;const ll LINF = 2001002003004005006ll;const int INF = 1001001001;#ifdef MY_LOCAL_DEBUG#include "./debug/localDebug.cpp"#define showp(p) cerr<<#p<<" = "<<p.fi<<" : "<<p.se<<endl#define show1(a) cerr<<#a<<" = "<<a<<endl#define show2(a,b) cerr<<#a<<" = "<<a<<" : "<<#b<<" = "<<b<<endl#define show3(a,b,c) cerr<<#a<<" = "<<a<<" : "<<#b<<" = "<<b<<" : "<<#c<<" = "<<c<<endl#define show4(a,b,c,d) cerr<<#a<<" = "<<a<<" : "<<#b<<" = "<<b<<" : "<<#c<<" = "<<c<<" : "<<#d<<" = "<<d<<endl#define show5(a,b,c,d,e) cerr<<#a<<" = "<<a<<" : "<<#b<<" = "<<b<<" : "<<#c<<" = "<<c<<" : "<<#d<<" = "<<d<<" : "<<#e<<" = "<<e<<endl#define DEBUG_LINE cout << "DEBUG_LINE : " << __LINE__ << endl#define showv(v) {cout<<#v<<" : "; fore(vy , v) {cout << vy << " ";} cout << endl;}#define showv2(v) {cout<<#v<<endl; fore(vy , v) cout << vy << "\n";}#define showvm(v) {cout<<#v<<" : "; fore(vy , v) {cout << vy.val() << " ";} cout << endl;}#define showvm2(v) {cout<<#v<<endl; fore(vy , v) cout << vy.val() << "\n";}#define showmat(v) {cout<<#v<<endl; fore(row , v) { fore(seg , row) cout << seg << " "; cout << endl;}}#define showmatm(v) {cout<<#v<<endl; fore(row , v) { fore(seg , row) cout << seg.val() << " "; cout << endl;}}#else#define showp(p)#define show1(a)#define show2(a,b)#define show3(a,b,c)#define show4(a,b,c,d)#define show5(a,b,c,d,e)#define DEBUG_LINE#define showv(v)#define showv2(v)#define showvm(v)#define showvm2(v)#define showmat(v)#define showmatm(v)#endif#define overload5(a,b,c,d,e,f, ...) f#define show(...) overload5(__VA_ARGS__, show5, show4, show3, show2, show1)(__VA_ARGS__)struct HeavyLightDecomposition{private:public:int _n;vvi _e;vi _size, _depth, _nxt, _par; // _nxt[x] : 頂点xと同じHeavyパスに含まれる頂点のうち、最も根に近い頂点の番号vi _up; // _up[x] : オイラ-ツアーにおける頂点xの帰りがけ時の順序番号。詳細は_dfs_hldを見る。vi down;// down[x] : オイラ-ツアーにおける頂点xの行きがけ時の順序番号。HeavyLightDecomposition(const vvi& _e, int root = 0) : _e(_e){_n = sz(_e);_id = 0;_size = vi(_n);_depth = vi(_n);down = vi(_n,-1);_up = vi(_n,-1);_nxt = vi(_n,root);_par = vi(_n,root);_dfs_sz(root);_dfs_hld(root);}private:int _id;void _dfs_sz(int x){_size[x] = 1;for(int& y : _e[x]){if (y == _par[x]){if (sz(_e[x])>=2 && y==_e[x][0]){swap(_e[x][0], _e[x][1]);}else{continue;}}_depth[y] = _depth[x] + 1;_par[y] = x;_dfs_sz(y);_size[x] += _size[y];if (_size[y] > _size[_e[x][0]]) swap(y, _e[x][0]);}}void _dfs_hld(int x){down[x] = _id++;for (int& y : _e[x]){if (y == _par[x]) continue;_nxt[y] = (y == _e[x][0]) ? _nxt[x] : y;_dfs_hld(y);}_up[x] = _id;}// [u, v)vpii _ascend(int a, int b) const {vpii res;while (_nxt[a]!=_nxt[b]){res.emplace_back(down[a], down[_nxt[a]]);a = _par[_nxt[a]];}if (a != b) res.emplace_back(down[a], down[b] + 1);return res;}// (u, v]vpii _descend(int a, int b) const {if (a == b) return {};if (_nxt[a] == _nxt[b]) return {{down[a] + 1, down[b]}};vpii res = _descend(a, _par[_nxt[b]]);res.emplace_back(down[_nxt[b]], down[b]);return res;}public:template <typename F>void path_query(int u, int v, bool vertex, const F &f){int l = lca(u, v);for (auto &&[a, b] : _ascend(u, l)){int s = a + 1, t = b;s > t ? f(t, s) : f(s, t);}if (vertex) f(down[l], down[l] + 1);for (auto &&[a, b] : _descend(l, v)){int s = a, t = b + 1;s > t ? f(t, s) : f(s, t);}}template <typename F>void subtree_query(int u, bool vertex, const F &f){f(down[u] + int(!vertex), _up[u]);}int lca(int a, int b){while (_nxt[a] != _nxt[b]){if (down[a] < down[b]) swap(a, b);a = _par[_nxt[a]];}return _depth[a] < _depth[b] ? a : b;}int dist(int a, int b) { return _depth[a] + _depth[b] - _depth[lca(a, b)] * 2; }};// HeavyLightDecomposition// [remark]// HLD分解。木をオイラーツアーで列化し効率的に分解する。// クエリを適用したい列データ構造(セグ木など)は本クラスとは別に持ち、ラムダ式などを介して作用させる。// 頂点・辺の双方に対応している。辺に適用する場合は辺を子側頂点に連動させると考えやすくなる。//// [interface]// HeavyLightDecomposition(const vvi& _e, int root = 0) : eは木の隣接頂点リスト,rootは根// path_query(int u, int v, bool vertex, const F &f) : パス[u,v]にクエリfを適用させる。vertexは頂点に対するクエリかどうか。// void subtree_query(int u, bool vertex, const F &f) : 頂点uの部分木にクエリfを適用させる。// int lca(a,b) : a,bのlca// int dist(int a, int b) : パス[a,b]の長さvoid solve(){int n,q; cin>>n>>q;vl a(n);vl sum(n);rep(i,n) cin>>a[i];vvi e(n),e_big(n);rep(i,n-1){int a,b; cin>>a>>b;a--; b--;e[a].pb(b);e[b].pb(a);}vb flg(n);vi bigs;const int c = sqrt(n) + 1;rep(i,n){if (sz(e[i])>=c){flg[i] = true;bigs.pb(i);}}rep(i,n){fore(y , e[i]){if (!flg[y]) continue;e_big[i].pb(y);}}rep(i,n){fore(y , e[i]){if (flg[y]) continue;sum[i] += a[y];}}fenwick_tree<ll> fw_sum(n+1),fw(n);HeavyLightDecomposition h(e);rep(i,n) if (!flg[i]) fw.add(h.down[i], a[i]);rep(i,n) fw_sum.add(h.down[i], sum[i]);auto IsOnPath = [&](int u, int v, int target)->bool{if (u==target || v==target) return true;if (h.lca(u,v) == target) return true;bool ok1 = false;bool ok2 = false;if (h.lca(target, u) == target) ok1 = true;else ok2 = true;if (h.lca(target, v) == target) ok1 = true;else ok2 = true;return (ok1 && ok2);};vl ans;rep(i,q){int t; cin>>t;if (t == 0){int v; cin>>v;v--;ll x; cin>>x;a[v] += x;if (flg[v]){}else{fw.add(h.down[v], x);fore(y , e[v]){sum[y] += x;fw_sum.add(h.down[y], x);}}}else{int u,v; cin>>u>>v;u--; v--;ll tmp = 0;auto f = [&](int a,int b)->void{tmp += fw_sum.sum(a,b);tmp -= fw.sum(a,b);};h.path_query(u, v, true, f);if (!flg[u]) tmp += a[u];if (!flg[v]) tmp += a[v];fore(y, bigs){bool ok = false;if (IsOnPath(u,v,y)) ok = true;int c = h.lca(u,v);if (h._par[c]==y) ok = true;if (h._par[y]!=-1 && IsOnPath(u,v,h._par[y])) ok = true;if (ok) tmp += a[y];}ans.pb(tmp);}}outv;return;}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin>>t;rep(i,t){solve();}return 0;}