The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online B Red Black Tree （LCA）

题目链接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5807

题意：

给一棵n个节点的红黑树，每条边有距离。树上有m个点是红的，每个红点的cost是0，每个黑点的cost是离它最近的红点祖先到它的距离。

q个询问，每次给k个点，现在允许你将树上某个点变红，是这k个点的cost的最大值最小，输出这个值。（数据规模都是10w）

思路1：

把每个红点与它父亲断开，这样就有很多棵根节点红色其他节点黑色的树（红根树）。

每次询问k个点，我们只需要考虑它们所在的红根树当中，max(cost)最大和次大的两棵树。

现在要选某个点变红，肯定是选在最大的红根树里。将max(cost)最小化后，和次大的树比一下就行了。

问题转化成，在红根树里选一个点变红，使k'个点的max(cost)最小。那就把k'个点按cost从小到大排序，求k'个后缀LCA就行了。

（可惜比赛的时候一句话写错了，搞半天还以为思路错了）

复杂度：O(n*log(n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;
const int N=100005;
int red[N];
int redfa[N];
vector<P>link[N];
ll cost[N];
int deep[N];
int sz[N],son[N],fa[N];
void dfs(int u,int _fa,int _red,ll _cost,int _deep){
	fa[u]=_fa;
	deep[u]=_deep;
	cost[u]=_cost;
	redfa[u]=_red;
	sz[u]=1;
	son[u]=-1;
	for (P p:link[u]){
		int v=p.first; ll w=p.second;
		if (v==_fa) continue;
		if (red[v]) dfs(v,u,v,0,_deep+1);
		else dfs(v,u,_red,_cost+w,_deep+1);
		sz[u]+=sz[v];
		if (son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
	}
}
int top[N],id[N],T;
void dfs2(int u,int _fa,int p){
    top[u]=p;
    id[u]=++T;
    if (son[u]!=-1) dfs2(son[u],u,p);
	for (P p:link[u]){
		int v=p.first; ll w=p.second;
        if (v==_fa||v==son[u]) continue;
        dfs2(v,u,v);
    }
}
int getlca(int x,int y){
	if (x==0) return y;
    int f1=top[x],f2=top[y];
    while(f1!=f2){
        if (deep[f1]<deep[f2]) swap(f1,f2),swap(x,y);
        x=fa[f1],f1=top[x];
    }
    if (deep[x]<deep[y]) swap(x,y);
    return y;
}
int stk[N];
int que[N];
ll f[N];
vector<int>VS[N];
int vis[N];
bool cmp(int i,int j){
	return f[i]>f[j];
}
bool cmp2(int i,int j){
	return cost[i]<cost[j];
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		int n,m,q; scanf("%d%d%d",&n,&m,&q);
		for (int i=1;i<=m;i++){
			int x; scanf("%d",&x);
			red[x]=1;
		}
		for (int i=1;i<n;i++){
			int x,y; ll w; scanf("%d%d%lld",&x,&y,&w);
			link[x].push_back({y,w});
			link[y].push_back({x,w});
		}
		dfs(1,0,1,0,1);
		dfs2(1,0,1);
		for (int T=1;T<=q;T++){
			int num; scanf("%d",&num);
			int top=0;
			for (int i=1;i<=num;i++){
				scanf("%d",&que[i]);
				int _red=redfa[que[i]];
				VS[_red].emplace_back(que[i]);
				if (vis[_red]!=T) stk[++top]=_red,f[_red]=cost[que[i]];
				else f[_red]=max(f[_red],cost[que[i]]);
				vis[_red]=T;
			}
			sort(stk+1,stk+top+1,cmp);
			int _red=stk[1];
			sort(VS[_red].begin(),VS[_red].end(),cmp2);
			int tot=VS[_red].size();
			ll ret = cost[VS[_red][tot - 1]];
			int lca=VS[_red][tot - 1];
			for (int i=tot-1;i>=0;i--){
				lca=getlca(lca,VS[_red][i]);
				ll tmp;
				if (i!=0) tmp=cost[VS[_red][i-1]];
				else tmp=0;
				ret=min(ret,max(tmp,f[_red]-cost[lca]));
			}
			if (top==1) printf("%lld\n",ret);
			else printf("%lld\n",max(ret,f[stk[2]]));
			for (int i=1;i<=top;i++) VS[stk[i]].clear();
		}
		for (int i=1;i<=n;i++){
			link[i].clear();
			red[i]=0;
			vis[i]=0;
		}
	}
}

思路2：

二分答案，不满足答案的LCA合并起来再看是否满足。（大家基本是这么做的）

复杂度：O(n*log(1e14)*log(n))     但是树链剖分求LCA实在是太快了，也能过

求LCA的地方还可以转RMQ用ST表做到O（1），就是写起来比较麻烦

（试了下倍增求LCA，T掉了，果然树剖大法好！）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;
const int N=100005;
int red[N];
int redfa[N];
vector<P>link[N];
ll cost[N];
int deep[N];
int que[N];
int sz[N],son[N],fa[N];
void dfs(int u,int _fa,int _red,ll _cost,int _deep){
	fa[u]=_fa;
	deep[u]=_deep;
	cost[u]=_cost;
	redfa[u]=_red;
	sz[u]=1;
	son[u]=-1;
	for (P p:link[u]){
		int v=p.first; ll w=p.second;
		if (v==_fa) continue;
		if (red[v]) dfs(v,u,v,0,_deep+1);
		else dfs(v,u,_red,_cost+w,_deep+1);
		sz[u]+=sz[v];
		if (son[u]==-1||sz[v]>sz[son[u]]) son[u]=v;
	}
}
int top[N],id[N],T;
void dfs2(int u,int _fa,int p){
    top[u]=p;
    id[u]=++T;
    if (son[u]!=-1) dfs2(son[u],u,p);
	for (P p:link[u]){
		int v=p.first; ll w=p.second;
        if (v==_fa||v==son[u]) continue;
        dfs2(v,u,v);
    }
}
int getlca(int x,int y){
	if (x==0) return y;
    int f1=top[x],f2=top[y];
    while(f1!=f2){
        if (deep[f1]<deep[f2]) swap(f1,f2),swap(x,y);
        x=fa[f1],f1=top[x];
    }
    if (deep[x]<deep[y]) swap(x,y);
    return y;
}
bool check(ll len,int num){
	int lca=0;
	for (int i=1;i<=num;i++)
		if (cost[que[i]]>len) lca=getlca(lca,que[i]);
	for (int i=1;i<=num;i++)
		if (cost[que[i]]>len){
			if (deep[redfa[que[i]]]>=deep[lca]) return 0;
			if (cost[que[i]]-cost[lca]>len) return 0;
		}
	return 1;
}
int main(){
	int t; scanf("%d",&t);
	while(t--){
		int n,m,q; scanf("%d%d%d",&n,&m,&q);
		for (int i=1;i<=m;i++){
			int x; scanf("%d",&x);
			red[x]=1;
		}
		for (int i=1;i<n;i++){
			int x,y; ll w; scanf("%d%d%lld",&x,&y,&w);
			link[x].push_back({y,w});
			link[y].push_back({x,w});
		}
		dfs(1,0,1,0,1);
		dfs2(1,0,1);
		for (int T=1;T<=q;T++){
			int num; scanf("%d",&num);
			for (int i=1;i<=num;i++) scanf("%d",&que[i]);
			ll l=0,r=1e14;
			while(l<r){
				ll mid=(l+r)/2;
				if (!check(mid,num)) l=mid+1;
				else r=mid;
			}
			printf("%lld\n",l);
		}
		for (int i=1;i<=n;i++){
			link[i].clear();
			red[i]=0;
			deep[i]=0;
		}
	}
}