結果
問題 | No.1216 灯籠流し/Lanterns |
ユーザー |
![]() |
提出日時 | 2020-08-30 16:03:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 9,783 bytes |
コンパイル時間 | 5,020 ms |
コンパイル使用メモリ | 280,872 KB |
最終ジャッジ日時 | 2025-01-13 23:31:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 TLE * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}struct Sack{using F = function<void(int)>;int n;vector<int> sz,hvy,big;vector<vector<int> > G,Q;F expand,shrink,query,reset;Sack(int n,F expand,F shrink,F query,F reset):sz(n,1),hvy(n,-1),big(n,0),G(n),Q(n),expand(expand),shrink(shrink),query(query),reset(reset){}void add_edge(int u,int v){G[u].emplace_back(v);G[v].emplace_back(u);}void add_query(int v,int k){Q[v].emplace_back(k);sz[v]++;}void add(int v,int p,int x){if(x==1) expand(v);else shrink(v);for(int u:G[v])if(u!=p&&!big[u]) add(u,v,x);}void dfs(int v=0,int p=-1,bool k=0){for(int u:G[v])if(u!=p&&u!=hvy[v]) dfs(u,v,0);if(~hvy[v]){dfs(hvy[v],v,1);big[hvy[v]]=1;}add(v,p,1);for(int k:Q[v]) query(k);if(~hvy[v]) big[hvy[v]]=0;if(!k) add(v,p,0),reset(v);}void build(int v=0,int p=-1){for(int u:G[v]){if(u==p) continue;build(u,v);if(hvy[v]<0||sz[hvy[v]]<sz[u]) hvy[v]=u;sz[v]+=sz[u];}if(p==-1) dfs(v,p);}};class EulerTourForVertex{private:vector<int> ls,rs;int pos;void dfs(int v,int p){ls[v]=pos++;for(int u:G[v])if(u!=p) dfs(u,v);rs[v]=pos;}public:vector< vector<int> > G;EulerTourForVertex(){}EulerTourForVertex(int n):ls(n),rs(n),G(n){}void add_edge(int u,int v){G[u].emplace_back(v);G[v].emplace_back(u);}void build(int r=0){pos=0;dfs(r,-1);}int idx(int v){return ls[v];}template<typename F>void exec(int v,F f){f(ls[v],rs[v]);}};struct LowestCommonAncestor{int n,h;vector< vector<int> > G,par;vector<int> dep;LowestCommonAncestor(){}LowestCommonAncestor(int n):n(n),G(n),dep(n){h=1;while((1<<h)<=n) h++;par.assign(h,vector<int>(n,-1));}void add_edge(int u,int v){G[u].emplace_back(v);G[v].emplace_back(u);}void dfs(int v,int p,int d){par[0][v]=p;dep[v]=d;for(int u:G[v])if(u!=p) dfs(u,v,d+1);}void build(int r=0){dfs(r,-1,0);for(int k=0;k+1<h;k++)for(int v=0;v<n;v++)if(~par[k][v])par[k+1][v]=par[k][par[k][v]];}int lca(int u,int v){if(dep[u]>dep[v]) swap(u,v);for(int k=0;k<h;k++)if((dep[v]-dep[u])>>k&1)v=par[k][v];if(u==v) return u;for(int k=h-1;k>=0;k--)if(par[k][u]!=par[k][v])u=par[k][u],v=par[k][v];return par[0][u];}int distance(int u,int v){return dep[u]+dep[v]-dep[lca(u,v)]*2;}};struct AuxiliaryTree : EulerTourForVertex{using super = EulerTourForVertex;LowestCommonAncestor lca;vector<vector<int>> T;AuxiliaryTree(){}AuxiliaryTree(int n):super(n),lca(n),T(n){}void build(int r=0){super::build(r);lca.G=super::G;lca.build(r);}void add_aux_edge(int u,int v){T[u].emplace_back(v);T[v].emplace_back(u);}using super::idx;void query(vector<int> &vs){assert(!vs.empty());sort(vs.begin(),vs.end(),[&](int a,int b){return idx(a)<idx(b);});vs.erase(unique(vs.begin(),vs.end()),vs.end());int k=vs.size();stack<int> st;st.emplace(vs[0]);for(int i=0;i+1<k;i++){int w=lca.lca(vs[i],vs[i+1]);if(w!=vs[i]){int l=st.top();st.pop();while(!st.empty()&&lca.dep[w]<lca.dep[st.top()]){add_aux_edge(st.top(),l);l=st.top();st.pop();}if(st.empty()||st.top()!=w){st.emplace(w);vs.emplace_back(w);}add_aux_edge(w,l);}st.emplace(vs[i+1]);}while(st.size()>1){int c=st.top();st.pop();add_aux_edge(st.top(),c);}}void clear(const vector<int> &ws){for(int w:ws) T[w].clear();}};template<typename T>struct RangeCount{struct BIT{vector<T> dat;BIT(){}BIT(int n){dat.assign(++n,0);}T sum(int k){T res=0;for(;k;k-=k&-k) res+=dat[k];return res;}void add(int k,T v){for(++k;k<(int)dat.size();k+=k&-k) dat[k]+=v;}};int n;using ll = long long;vector< vector<ll> > val;vector<BIT> dat;RangeCount(){}RangeCount(int n_){n=1;while(n<n_) n<<=1;val.assign(n<<1,vector<ll>());dat.reserve(n<<1);}void preupdate(int a,ll x){a+=n;while(a){val[a].emplace_back(x);a>>=1;}}void build(){for(int i=0;i<n*2;i++){auto &v=val[i];sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());dat.emplace_back(v.size());}}void update(int a,ll x,T z){a+=n;while(a){auto &v=val[a];int k=lower_bound(v.begin(),v.end(),x)-v.begin();dat[a].add(k,z);a>>=1;}}T calc(int k,ll x,ll y){auto &v=val[k];int p=lower_bound(v.begin(),v.end(),x)-v.begin();int q=lower_bound(v.begin(),v.end(),y)-v.begin();return dat[k].sum(q)-dat[k].sum(p);}// [a, b) * [x, y)T query(int a,int b,ll x,ll y){T res=0;for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1){if(l&1) res+=calc(l++,x,y);if(r&1) res+=calc(--r,x,y);}return res;}};template<typename TV, const int N> void read_tuple_impl(TV&) {}template<typename TV, const int N, typename Head, typename... Tail>void read_tuple_impl(TV& ts) {get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));read_tuple_impl<TV, N+1, Tail...>(ts);}template<typename... Ts> decltype(auto) read_tuple(size_t n) {tuple<vector<Ts>...> ts;for(size_t i=0;i<n;i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);return ts;}template<typename F>struct FixPoint : F{FixPoint(F&& f):F(forward<F>(f)){}template<typename... Args>decltype(auto) operator()(Args&&... args) const{return F::operator()(*this,forward<Args>(args)...);}};template<typename F>inline decltype(auto) MFP(F&& f){return FixPoint<F>{forward<F>(f)};}template<typename V>V compress(V vs){sort(vs.begin(),vs.end());vs.erase(unique(vs.begin(),vs.end()),vs.end());return vs;}template<typename T>map<T, int> dict(const vector<T> &vs){map<T, int> res;for(int i=0;i<(int)vs.size();i++)res[vs[i]]=i;return res;}map<char, int> dict(const string &s){return dict(vector<char>(s.begin(),s.end()));}using i16 = int16_t;using i32 = int32_t;using i64 = int64_t;using u16 = uint16_t;using u32 = uint32_t;using u64 = uint64_t;// AtCoderconst i64 CYCLES_PER_SEC = 2800000000;struct Timer {i64 start;Timer(){reset();}void reset(){start=getCycle();}inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}inline i64 getCycle(){u32 low,high;__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));return ((i64)low)|((i64)high<<32);}};Timer timer;//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);using ll = long long;int n,q;cin>>n>>q;using P = pair<int, ll>;vector<vector<P>> G(n);AuxiliaryTree H(n);for(int i=1;i<n;i++){int a,b;ll c;cin>>a>>b>>c;a--;b--;G[a].emplace_back(b,c);G[b].emplace_back(a,c);H.add_edge(a,b);}H.build(0);vector<ll> dep(n);MFP([&](auto dfs,int v,int p,ll d)->void{dep[v]=d;for(auto [u,c]:G[v])if(u!=p) dfs(u,v,d+c);})(0,-1,0);auto [type,vs,ts,ls]=read_tuple<int, int, ll, ll>(q);for(int &v:vs) v--;vector<int> ans(q);queue<P> que;que.emplace(0,q);while(!que.empty()){if(timer.get()>4.0) break;auto [L,R]=que.front();que.pop();if(L+1==R) continue;int M=(L+R)>>1;vector<int> ss;for(int i=L;i<M;i++)if(type[i]==0) ss.emplace_back(vs[i]);for(int i=M;i<R;i++)if(type[i]==1) ss.emplace_back(vs[i]);if(ss.empty()){que.emplace(L,M);que.emplace(M,R);continue;}ss.emplace_back(0);H.query(ss);ss=compress(ss);auto dc=dict(ss);int m=ss.size();vector<vector<int>> B(m);for(int i=L;i<M;i++)if(type[i]==0) B[dc[vs[i]]].emplace_back(i);vector<ll> pos;for(int i=L;i<M;i++)if(type[i]==0) pos.emplace_back(ts[i]+dep[vs[i]]);for(int i=M;i<R;i++)if(type[i]==1) pos.emplace_back(ts[i]+dep[vs[i]]);pos=compress(pos);auto rev=dict(pos);RangeCount<int> seg(pos.size());for(int i=L;i<M;i++)if(type[i]==0)seg.preupdate(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i]);seg.build();auto expand=[&](int v){for(int i:B[v])seg.update(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i],+1);};auto shrink=[&](int v){for(int i:B[v])seg.update(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i],-1);};auto query=[&](int i){if(type[i]==1)ans[i]+=seg.query(0,rev[ts[i]+dep[vs[i]]]+1,-1e18,dep[vs[i]]+1);};auto reset=[&](int){};Sack S(m,expand,shrink,query,reset);for(int v:ss)for(int u:H.T[v])if(v<u) S.add_edge(dc[u],dc[v]);for(int i=L;i<M;i++)if(type[i]==0) S.add_query(dc[vs[i]],i);for(int i=M;i<R;i++)if(type[i]==1) S.add_query(dc[vs[i]],i);S.build(dc[0]);H.clear(ss);que.emplace(L,M);que.emplace(M,R);}for(int i=0;i<q;i++)if(type[i]==1) cout<<ans[i]<<newl;return 0;}