結果
| 問題 | No.1216 灯籠流し/Lanterns |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-09-03 09:45:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 452 ms / 4,500 ms |
| コード長 | 4,959 bytes |
| コンパイル時間 | 1,957 ms |
| コンパイル使用メモリ | 148,372 KB |
| 最終ジャッジ日時 | 2025-01-14 04:05:52 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 48 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;struct HeavyLightDecomposition{vector<vector<pair<int, ll>>> g;vector<int> in, out, rev, cnt, head, par;vector<ll> d, drev;HeavyLightDecomposition(const vector<vector<pair<int, ll>>> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()),par(g.size()), d(g.size()), drev(g.size()){}void dfs(int x, int p){cnt[x]=1, par[x]=p;int mx=-1, k=-1;for(int i=0; i<g[x].size(); i++){int y=g[x][i].first;if(y==p) continue;d[y]=d[x]+g[x][i].second;dfs(y, x);cnt[x]+=cnt[y];if(mx<cnt[y]) mx=cnt[y], k=i;}if(k>0) swap(g[x][k], g[x][0]);}void dfs2(int x, int p, int &t){in[x]=t++;rev[in[x]]=x;for(int i=0; i<g[x].size(); i++){int y=g[x][i].first;if(y==p) continue;if(i) head[y]=y;else head[y]=head[x];dfs2(y, x, t);}out[x]=t;}void build(){int t=0;dfs(0, -1);dfs2(0, -1, t);for(int i=0; i<d.size(); i++) drev[in[i]]=d[i];}int la(int v, ll k){while(1){int u=head[v];if(u!=0 && d[v]-k<=d[par[u]]){k-=d[v]-d[par[u]];v=par[u];continue;}int t=lower_bound(drev.begin()+in[u], drev.begin()+in[v]+1, d[v]-k)-drev.begin();return rev[t];}}template<typename Q>void query(int u, int v, const Q &q){//T ret=e;for(; ; v=par[head[v]]){if(in[u]>in[v]) swap(u, v);if(head[u]==head[v]) break;q(in[head[v]], in[v]+1);//ret=f(q(in[head[v]], in[v]+1), ret);}q(in[u], in[v]+1);//ret=f(q(in[u], in[v]+1), ret);//return ret;}};template<typename T>struct BIT{vector<T> bit;int size;BIT(){}BIT(int n):size(n), bit(n+1, 0){}void init(int n){size=n;bit.resize(n+1, 0);}T sum(int i){ //[0, i)T s=0;while(i>0){s+=bit[i];i-=(i&(-i));}return s;}T sum(int l, int r){ //[l, r)return sum(r)-sum(l);}void add(int i, T x){i++;while(i<=size){bit[i]+=x;i+=(i&(-i));}}};int main(){int n, q; cin>>n>>q;vector<vector<pair<int, ll>>> g(n);for(int i=0; i<n-1; i++){int a, b; ll c;cin>>a>>b>>c;a--; b--;g[a].push_back({b, c});g[b].push_back({a, c});}HeavyLightDecomposition hld(g);hld.build();int type[100010], v[100010], h[100010];ll t[100010], l[100010];int sz=1;while(sz<n) sz<<=1;vector<vector<ll>> seg(2*sz);auto add0=[&](int l, int r, ll x){l+=sz, r+=sz;for(;l<r; l>>=1, r>>=1){if(r&1) seg[--r].push_back(x);if(l&1) seg[l++].push_back(x);}};for(int i=0; i<q; i++){cin>>type[i]>>v[i]>>t[i]>>l[i];v[i]--;if(type[i]==0){h[i]=hld.la(v[i], l[i]);auto qr0=[&](int l, int r){add0(l, r, hld.d[v[i]]+t[i]);};hld.query(h[i], v[i], qr0);}}vector<BIT<int>> bit(2*sz);for(int i=1; i<2*sz; i++){sort(seg[i].begin(), seg[i].end());seg[i].erase(unique(seg[i].begin(), seg[i].end()), seg[i].end());bit[i].init((int)seg[i].size());}auto add=[&](int l, int r, ll x){l+=sz, r+=sz;for(;l<r; l>>=1, r>>=1){if(r&1){r--;int p=lower_bound(seg[r].begin(), seg[r].end(), x)-seg[r].begin();bit[r].add(p, 1);}if(l&1){int p=lower_bound(seg[l].begin(), seg[l].end(), x)-seg[l].begin();bit[l].add(p, 1);l++;}}};for(int i=0; i<q; i++){if(type[i]==0){auto qr=[&](int l, int r){add(l, r, hld.d[v[i]]+t[i]);};hld.query(h[i], v[i], qr);}else{int p=hld.in[v[i]];ll x=hld.d[v[i]]+t[i];p+=sz;int q=upper_bound(seg[p].begin(), seg[p].end(), x)-seg[p].begin();int ans=bit[p].sum(q);while(p>1){p>>=1;q=upper_bound(seg[p].begin(), seg[p].end(), x)-seg[p].begin();ans+=bit[p].sum(q);}printf("%d\n", ans);}}return 0;}