Red Black Tree ZOJ - 4048

LCA+二分

 #include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lowbit(x) (x&(-x)) #define Pb push_back #define FI first #define SE second #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define IOS ios::sync_with_stdio(false) #define DEBUG cout<<endl<<"DEBUG"<<endl;  using namespace std; typedef long long LL; typedef unsigned long long ULL; const int prime = 999983; const int INF = 0x7FFFFFFF; const LL INFF =0x7FFFFFFFFFFFFFFF; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-6; const LL mod = 1e9 + 7; LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;} LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;} int dr[2][4] = {1,-1,0,0,0,0,-1,1}; typedef pair<int,int> P; const int maxn = 2e5+100; const int maxlogv = 19; bool red[maxn]; struct Edge{ int to,weight; Edge(int t,int w):to(t),weight(w){}; }; vector<Edge> G[maxn]; int id[maxn]; LL dis[maxn]; LL dist[maxn]; int vs[maxn*2],depth[maxn*2]; int dp[maxn*2][maxlogv]; void dfs(int node,int fa,int d,int &k){ id[node] = k; vs[k] = node; depth[k++] = d; // dis[node] = distance; for(int i = 0;i < G[node].size(); ++i){ Edge &t = G[node][i]; if(t.to == fa) continue; if(!red[t.to]) dis[t.to] = dis[node]+t.weight; else dis[t.to] = 0; dist[t.to] = dist[node] + t.weight; // cout<<dis[t.to]<<endl; // cout<<t.weight<<endl; dfs(t.to,node,d+1,k); vs[k] = node; depth[k++] = d; } } void init_rmq(int n){ for(int i = 0;i < n ; ++i) dp[i][0] = i; for(int j = 1;(1<<j) <= n; ++j){ for(int i = 0;i + (1<<j)-1 < n; ++i){ if(depth[dp[i][j-1]]< depth[dp[i+(1<<(j-1))][j-1]]) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i+(1<<(j-1))][j-1]; } } } int query(int l,int r){ int k = 0; while((1<<(k+1)) <= r-l+1) k++; if(depth[dp[l][k]] < depth[dp[r-(1<<k)+1][k]]) return dp[l][k]; else return dp[r-(1<<k)+1][k]; } int lca(int u,int v){ return vs[query(min(id[u],id[v]),max(id[u],id[v]))]; } // const int maxn = 1e5+1000; //  int b[maxn]; bool check(int kk,LL mid){ bool yes = true; int fa; for(int i = 1;i <= kk; ++i){ if(dis[b[i]] > mid){ if(yes){ yes = false; fa = b[i]; } else fa = lca(fa,b[i]); } } if(yes) return true; for(int i = 1;i <= kk; ++i){ if(dis[b[i]] > mid){ if(dist[b[i]] - dist[fa] > mid) return false; } } return true; } // #define Debug int main(void) { #ifdef Debug freopen("input.txt","r",stdin); freopen("output.txt","w+",stdout); #endif int T; int n,m,q; cin>>T; while(T--){ me(red); scanf("%d%d%d",&n,&m,&q); for(int i = 0;i < n; ++i) G[i].clear(); for(int i = 0;i < m; ++i) { int a; scanf("%d",&a); a--; red[a] = true; } for(int i = 1;i < n; ++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--,v--; G[u].Pb(Edge(v,w)); // cout<<w<<endl; G[v].Pb(Edge(u,w)); } int k = 0; dfs(0,-1,0,k); init_rmq(2*n-1); // /*for(int i = 0;i < n; ++i )cout<<dis[i]<<" "; while(q--){ int kk; scanf("%d",&kk); for(int i = 1;i <= kk;++i) scanf("%d",&b[i]),b[i]--; LL l = 0,r = 1e14; while(r >= l){ LL mid = (r+l)>>1; if(check(kk,mid)){ r = mid-1; } else l = mid+1; } printf("%lld\n",l); } } return 0; }