제출 #922339

#제출 시각아이디문제언어결과실행 시간메모리
922339pccRoadside Advertisements (NOI17_roadsideadverts)C++14
100 / 100
234 ms11356 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 5e4+10; int N,Q; vector<pii> tree[mxn]; ll segtree[mxn*4]; int idx[mxn],par[mxn],sz[mxn],bs[mxn],link_top[mxn],dep[mxn],val[mxn],arr[mxn],cnt; vector<pll> st; void modify(int now,int l,int r,int s,int e){ if(!segtree[now])return; if(l>=s&&e>=r){ st.push_back(make_pair(now,segtree[now])); segtree[now] = 0; return; } int mid = (l+r)>>1; if(mid>=s)modify(now*2+1,l,mid,s,e); if(mid<e)modify(now*2+2,mid+1,r,s,e); st.push_back(make_pair(now,segtree[now])); segtree[now] = segtree[now*2+1]+segtree[now*2+2]; } ll getval(int now,int l,int r,int s,int e){ if(l>=s&&e>=r)return segtree[now]; else if(!segtree[now])return 0ll; int mid = (l+r)>>1; if(mid>=e)return getval(now*2+1,l,mid,s,e); else if(mid<s)return getval(now*2+2,mid+1,r,s,e); else return getval(now*2+1,l,mid,s,e)+getval(now*2+2,mid+1,r,s,e); } void build(int now,int l,int r){ if(l==r){ segtree[now] = val[l]; return; } int mid = (l+r)>>1; build(now*2+1,l,mid); build(now*2+2,mid+1,r); segtree[now] = segtree[now*2+1]+segtree[now*2+2]; return; } void dfs1(int now){ sz[now] = 1; for(auto nxt:tree[now]){ if(nxt.fs == par[now])continue; par[nxt.fs] = now; arr[nxt.fs] = nxt.sc; dep[nxt.fs] = dep[now]+1; dfs1(nxt.fs); sz[now] += sz[nxt.fs]; if(!bs[now]||sz[bs[now]]<sz[nxt.fs])bs[now] = nxt.fs; } return; } void dfs2(int now,int top){ idx[now] = ++cnt; val[cnt] = arr[now]; link_top[now] = top; if(bs[now])dfs2(bs[now],top); for(auto nxt:tree[now]){ if(nxt.fs == par[now]||nxt.fs == bs[now])continue; dfs2(nxt.fs,nxt.fs); } return; } ll lca(int a,int b){ int ta = link_top[a],tb = link_top[b]; ll re = 0; while(ta != tb){ if(dep[ta]<dep[tb]){ swap(a,b); swap(ta,tb); } re += getval(0,1,N,idx[ta],idx[a]); modify(0,1,N,idx[ta],idx[a]); a = par[ta]; ta = link_top[a]; } if(dep[a]>dep[b])swap(a,b); if(a != b){ re += getval(0,1,N,idx[a]+1,idx[b]); modify(0,1,N,idx[a]+1,idx[b]); } return re; } void segdfs(int now,int l,int r){ cout<<l<<' '<<r<<":"<<segtree[now]<<endl; if(l == r)return; int mid = (l+r)>>1; segdfs(now*2+1,l,mid); segdfs(now*2+2,mid+1,r); return; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N; for(int i = 1;i<N;i++){ int a,b,c; cin>>a>>b>>c; a++,b++; tree[a].push_back({b,c}); tree[b].push_back({a,c}); } dep[1] = 1; dfs1(1); dfs2(1,1); build(0,1,N); /* for(int i = 1;i<=N;i++)cout<<idx[i]<<' ';cout<<endl; for(int i = 1;i<=N;i++)cout<<val[i]<<' ';cout<<endl; segdfs(0,1,N); */ cin>>Q; while(Q--){ int req[5]; for(auto &i:req)cin>>i,i++; ll ans = 0; for(int i = 0;i<5;i++){ for(int j = i+1;j<5;j++){ ans += lca(req[i],req[j]); } } cout<<ans<<'\n'; while(!st.empty()){ segtree[st.back().fs] = st.back().sc; st.pop_back(); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...