题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18671145/
数据传送门:http://pan.baidu.com/s/1qYRC8w8
数据生成器:http://paste.ubuntu.com/18671482/
先来说一说lcr的很好想的做法,分类讨论:
1)联盟的所有城市,有一些在首都的子树外,一些在首都的子树内
2)首都在联盟形成伞形内,且子树中,无联盟的城市
3)首都和联盟完全独立
然后是分类处理:
1)用主席树查一查,这个答案是0
2)树上倍增,再利用主席树查一查
3)直接lca搞一搞
lcr的code:http://paste.ubuntu.com/18671740/
然后是std的算法,分类讨论同lcr,做法稍有不同:
1)这个可以不用主席树查,我们使用DFS序,二分找到小于首都的DFS序最大的一个,然后+1,即可判断
2)这个,我们还是用DFS序,找到小于首都最大的那个,然后+1,那么这两个一定是卡得最紧的两个,然后用LCA更新答案
3)直接lca搞一搞
这两种算法优越在,分来讨论以后,把一个帮派缩成了一个代表城市
std的算法优越在,神奇的DFS序,DFS离得近就是夹得紧
另外这种题目,反正不是分类讨论乱搞,就是分治,以后还是要多推推式子
递归版本:http://paste.ubuntu.com/18670939/
非递归版本:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAXN = 1000000+9;
const int INF = 100000000;
int n,T,head[MAXN],to[MAXN],nxt[MAXN],k,dep[MAXN],fa[MAXN][20],LC[MAXN];
int l[MAXN],r[MAXN],tot,cnt[MAXN],que[MAXN],*itr[MAXN],BUF[MAXN],now[MAXN];
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
inline void AddEdge(int a, int b){
to[++T] = b; nxt[T] = head[a]; head[a] = T;
to[++T] = a; nxt[T] = head[b]; head[b] = T;
}
inline void DFS(){
for (int i=1;i<=n;i++) now[i] = head[i];
int w = 1; tot = 1;
while (w) {
if (!now[w]) {
r[w] = tot;
w = fa[w][0];
} else {
if (!l[w]) l[w] = ++tot;
int tmp = to[now[w]]; now[w] = nxt[now[w]];
if (dep[tmp] != dep[w]+1) continue;
else w = tmp;
}
}
}
inline void BFS(){
BUF[1] = 1; dep[1] = 1;
for (int fro=1,bak=1;bak<=fro;bak++){
int w = BUF[bak];
for (int i=head[w];i;i=nxt[i]){
if (!dep[to[i]]) dep[to[i]] = dep[w]+1,
fa[to[i]][0] = w, BUF[++fro] = to[i];
}
}
}
inline bool cmp(const int &A, const int &B){
return l[A] < l[B];
}
inline int find(int *arr, int ri, int val){
if (l[arr[1]] >= val) return -1;
else {
int li=1,mid,ret;
while (li <= ri){
mid = (li+ri)/2;
if (l[arr[mid]] < val) li=mid+1,ret=mid;
else ri=mid-1;
}
return ret;
}
}
inline int LCA(int a, int b){
if (dep[a] < dep[b]) swap(a, b);
for (int i=18;i>=0;i--)
if (dep[fa[a][i]] >= dep[b])
a = fa[a][i];
if (a==b) return a;
else {
for (int i=18;i>=0;i--) if (fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
}
inline void init_LCA(){
for (int k=1;k<=18;k++) for (int i=1;i<=n;i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}
inline int DIS(int a, int b){
int lca = LCA(a, b);
return dep[a]+dep[b]-2*dep[lca];
}
inline void update(int *arr, int c, int v, int &ans, int lc){
int lca = LCA(lc, v);
if (lca == v) ans = min(ans, DIS(lc,v));
else if (lca != v && lca != lc) ans = min(ans, dep[lc]+dep[v]-2*dep[lca]);
else {
int tmp = find(arr,c,l[v]);
if (tmp==-1){
if (l[arr[1]] <= r[v] && l[arr] > r[v]) ans = 0;
else ans = min(ans, DIS(v,LCA(v,arr[1])));
} else {
if (tmp < c && l[arr[tmp+1]] <= r[v]) ans = 0;
else {
int lca = LCA(v,arr[tmp]);
ans = min(dep[v]-dep[lca], ans);
if (tmp < c){
lca = LCA(v,arr[tmp+1]);
ans = min(dep[v]-dep[lca], ans);
}
}
}
}
}
int main(){
freopen("alliances.in","r",stdin);
freopen("alliances.out","w",stdout);
srand(19991226); n = read();
for (int i=1;i<n;i++) AddEdge(read(),read());
BFS(); DFS(); itr[1] = que; init_LCA();
k = read(); for (int i=1;i<=k;i++) {
cnt[i] = read();
itr[i+1] = itr[i]+cnt[i];
for (int j=1,tmp;j<=cnt[i];j++) itr[i][j] = read();
int buf = itr[i][1];
for (int j=2;j<=cnt[i];j++) buf = LCA(buf, itr[i][j]);
LC[i] = buf; sort(itr[i]+1,itr[i]+cnt[i]+1,cmp);
}
for (int v,t,ans,Q=read();Q;Q--){
v = read(); t=read(); ans = INF;
for (int i=1,w;i<=t;i++){
w = read();
BUF[i] = itr[w][1];
update(itr[w], cnt[w], v, ans, LC[w]);
}
if (ans){
int buf = BUF[1];
for (int i=2;i<=t;i++) buf = LCA(buf, BUF[i]);
sort(BUF+1,BUF+t+1,cmp),
update(BUF, t, v, ans, buf);
}
printf("%d\n",ans);
}
return 0;
}
在%原教的代码的时候,发现了一点特殊的技能:
如果我们使用“当前弧”类似的技能,那么我们可以用一个BFS + while()很优雅的代替掉DFS()