tokitsukaze > ACM-ICPC 2018 青岛赛区网络预赛 B. Red Black Tree (二分答案+LCA)

ACM-ICPC 2018 青岛赛区网络预赛 B. Red Black Tree (二分答案+LCA)

2018-09-16

二分, LCA

转载请注明出处：http://tokitsukaze.live/

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4048

题意：
给一棵有根树，根为1。边有边权。其中m个节点是红色，其他节点是黑色。
有q次询问，每次查询给k个节点。然后你可以选择树上最多一个节点变成红色。设d[x]为节点x到离他最近的红色节点的距离，还要求红色节点必须是节点x的祖先。如果x是红色，那么d[x]=0。求出k个节点的max{d[i]}，使这个值最小化。

题解：
考虑答案是单调的，我们可以二分答案。
然后check，把询问的节点，如果满足就扔掉。最后把剩下这些不满足的，求个他们共同的LCA，那个点设为红点肯定最优，然后再判断是否满足。

dfs一遍可以预处理每个点的d[x]，用来判断是否满足。O(nlogn)预处理ST表，LCA就能O(1)查询了。然后求共同的LCA，可以直接for一遍，对当前LCA和点求LCA就行。(或者取出dfn(dfs序)最小和最大的点求一次LCA，一定就是所有的点的共同LCA。这样的话查询次数较少，可以O(n)做树链剖分，然后每次查询O(logn)。)

复杂度nlogn级别的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
	#ifdef tokitsukaze
		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=1e9+7;
/*********************************  head  *********************************/
struct node
{
	int to;
	ll w;
	node(){}
	node(int _to,ll _w) :to(_to),w(_w){}
};
ll dis[MAX],disred[MAX];
int path[2*MAX],deep[2*MAX],first[MAX],tot;
int dp[2*MAX][20];
bool flag[MAX];
vector<node> mp[MAX];
void dfs(int x,int pre,int h)
{
	int i;
	path[++tot]=x;
	first[x]=tot;
	deep[tot]=h;
	for(i=0;i<mp[x].size();i++)
	{
		int to=mp[x][i].to;
		if(to==pre) continue;
		disred[to]=min(disred[to],disred[x]+mp[x][i].w);
		dis[to]=dis[x]+mp[x][i].w;
		dfs(to,x,h+1);
		path[++tot]=x;
		deep[tot]=h;
	}
}
void ST(int n)
{
	int i,j,x,y;
	for(i=1;i<=n;i++)
	{
		dp[i][0]=i;
	}
	for(j=1;(1<<j)<=n;j++)
	{
		for(i=1;i+(1<<j)-1<=n;i++)
		{
			x=dp[i][j-1];
			y=dp[i+(1<<(j-1))][j-1];
			dp[i][j]=deep[x]<deep[y]?x:y;
		}
	}
}
int query(int l,int r)
{
	int len,x,y;
	len=(int)log2(r-l+1); 
	x=dp[l][len];
	y=dp[r-(1<<len)+1][len];
	return deep[x]<deep[y]?x:y;
}
int LCA(int x,int y)
{
	int l,r,pos;
	l=first[x];
	r=first[y];
	if(l>r) swap(l,r);
	pos=query(l,r);
	return path[pos];
} 
int getdist(int a,int b)
{
	return dis[a]+dis[b]-2*dis[LCA(a,b)];
}
void work(int n)
{
	int i;
	for(i=1;i<=n;i++) dis[i]=0;
	tot=0;
	dfs(1,0,0);
	ST(2*n-1);
}
int tmp[MAX];
void go()
{
	int t,n,m,q,i,a,b,w,k;
	ll l,r,mid;
	read(t);
	while(t--)
	{
		read(n,m,q);
		for(i=1;i<=n;i++)
		{
			mp[i].clear();
			disred[i]=LLINF;
		}
		while(m--)
		{
			read(a);
			disred[a]=0;
		}
		for(i=1;i<n;i++)
		{
			read(a,b,w);
			mp[a].pb(node(b,w));
			mp[b].pb(node(a,w));
		}
		work(n);
		while(q--)
		{
			read(k);
			l=r=0;
			for(i=1;i<=k;i++)
			{
				read(tmp[i]);
				r=max(r,dis[tmp[i]]);
			}
			VI res;
			auto check=[&](ll x)->int
			{
				res.clear();
				for(i=1;i<=k;i++)
				{
					if(disred[tmp[i]]>x) res.pb(tmp[i]);
				}
				if(sz(res)<=1) return 1;
				int lca=res[0];
				for(i=1;i<sz(res);i++) lca=LCA(lca,res[i]);
				for(i=0;i<sz(res);i++)
				{
					if(dis[res[i]]-dis[lca]>x) return 0;
				}
				return 1;
			};
			while(l<r)
			{
				mid=(l+r)>>1;
				if(check(mid)) r=mid;
				else l=mid+1;
			}
			printf("%lld\n",l);
		}
	}
}