Codeforces 588E Duff in the Army
西安邀请赛网络赛J的升级版本，要求输出具体的方案，这题就没办法离线水过去了。对dfs序建一个主席树，那么对于每个询问答案就是 $sum[u]+sum[v]-sum[lca(u,v)]-sum[fa[lca(u,v)]]$ 之后就不难了，实现起来比较复杂，不过写的蛮快的，wa了之后扫了一下主席树感觉没什么问题，就扫了一眼lca 发现最后求lca的部分写错了。
#include <bits/stdc++.h> using namespace std; #define dd(x) cout<<#x<<"="<<x<<" " #define rep(i,a,b) for(int i=(a);i<(b);i++) #define de(x) cout<<#x<<"="<<x<<"\n" #define mes(p) memset(p,0,sizeof(p)) #define fi first #define se second #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define sz(x) (int)x.size() #define pb push_back #define ls (rt<<1) #define rs (ls|1) #define all(x) x.begin(),x.end() const int maxn=100005; typedef long long ll; typedef vector <int > vi; typedef pair <int, int> pi; int dep[maxn], f[maxn][32],cnt, T[maxn]; int n, m, q; vector <int > num[maxn], v[maxn]; vector <int > ans; struct node{ int sum,l,r; node() {sum=l=r=0;} }t[maxn<<6]; void update(int pre,int &now,int l,int r,int pos){ now = ++cnt; t[now].sum = t[pre].sum+1; if(l==r) return ; t[now]. l = t[pre].l; t[now].r = t[pre].r; int mid = l+r >> 1; if(mid>=pos) update(t[pre].l,t[now].l,l,mid,pos); else update(t[pre].r,t[now].r,mid+1,r,pos); } void dfs(int x,int p,int d){ dep[x] = d; f[x][0] = p; rep(i,1,30) f[x][i] = f[f[x][i-1]][i-1]; T[x] = T[p]; for(auto u:num[x]) update(T[x],T[x],1,m,u); for(auto u:v[x]) if(u!=p) dfs(u,x,d+1); } int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); for(int i=29,d=dep[u]-dep[v];i>=0;i--) if(d>>i&1) u=f[u][i]; if(u==v) return v; for(int i=29;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i], v=f[v][i]; return f[u][0]; } void qr(int x,int y,int z,int d,int l,int r,int k){ int sl = t[t[x].l].sum + t[t[y].l].sum -t[t[z].l].sum - t[t[d].l].sum; if(l==r){ if(k)ans.pb(l); return ; } int mid = l+r >> 1; if(sl>=k) qr(t[x].l,t[y].l,t[z].l,t[d].l,l,mid,k); else { if(sl) qr(t[x].l,t[y].l,t[z].l,t[d].l,l,mid,sl); qr(t[x].r,t[y].r,t[z].r,t[d].r,mid+1,r,k-sl); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; rep(i,0,n-1){ int x,y; cin >> x >> y; v[x].pb(y); v[y].pb(x); } rep(i,0,m){ int x; cin >> x; num[x].pb(i+1); } dfs(1,1,0); rep(i,0,q){ int x,y,a; ans.clear(); cin >> x>>y>> a; int l=lca(x,y), d=f[l][0]; if(l==1) d=0; int k = min(a,t[T[x]].sum+t[T[y]].sum-t[T[l]].sum-t[T[d]].sum); qr(T[x],T[y],T[l],T[d],1,m,k); cout << sz(ans); for(auto i:ans )cout << " " <<i; cout << endl; } return 0; }转载于:https://www.cnblogs.com/seast90/p/10754163.html
