Codeforces round339 div1 D

처음으로 허수 문제를...
제목: 나무 한 그루를 주고 여러 번 물어보고 매번 k[i]개의 점을 준다. 이 점을 나무에서 분리하려면 최소한 몇 개의 점을 삭제해야 하는지 물어보고 k[i]의 점과 100000을 초과하지 않도록 한다.
우리는 먼저 허수를 세운 다음에 허수에 Dp를 세우면 된다. 우리는 Dp[i][0/1]를 설정한다. 만약에 0을 위해 이 점 트리의 모든 관건과 이 점이 끊어졌다는 것을 표시한다면 1은 이 점과 관련된 관건이 하나 더 있다는 것을 나타낸다.(두 점 이상일 수는 없다. 그렇지 않으면 비합법적이다.
그렇다면 지금이 관건이라면,
Dp[i][0]=inf,
Dp[i][1]=sigma(min(Dp[son][0], Dp[son][1]+1))이지만 현재 이 변의 변권이 1이면 Dp[son][0]로만 옮길 수 있다.
중요도가 아닌 경우 다음을 수행합니다.
S1=sigma(min(Dp[son][0], Dp[son][1])+1, 어쨌든 우리는 이 점을 직접 삭제하고 모두 Dp[son][0]인 상황을 고려하지 않는다.
S2=sigma(min(Dp[son][0], Dp[son][1]+1))는 이 점을 삭제하지 않고 아들과 연결된 허변의 점을 삭제한다는 뜻이다. 이와 같이 현재 이 변의 경계가 1이면 Dp[son][0]로만 이전할 수 있다.
우선 Dp[i][0]가 모두 Dp[son][0]에서 바뀌면 S2다. 그렇지 않으면 S1이 S2보다 더 좋을 것이다.
그래서 Dp[i][0]=min(S1,S2).
그리고 Dp[i][1]을 고려하면 Dp[i][0]의 조건에서 어떤min(Dp[son][0], Dp[son][1]+1)을 빼고 어떤 Dp[son][1]을 더하면 된다(이렇게 하면 단지 하나의 관건과 현재 점 i가 연결되는 것을 보장할 수 있다). 그래서 우리는 S1, S2를 기록할 때 이미min을 기록한다. Dp[son][1]-min(Dp[son][0], Dp[1][1]]을 기록할 수 있다. 만약에 현재 Dp[son]의 권리만 이전할 수 있다.
그리고 민(Dp[root][0], Dp[root]])이 답이다.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>
#define inf (long long)100000000
using namespace std;
struct node {int to;int next;int len;
};node edge[500010],bian[2000010];
int in[200010],out[200010],dep[200010],f[200010][21],root;
int tim = 0,fir[200010],first[200010],n,a,b,m,Q,stack[200010];
int sum=0,size=0,len,top,list[200010],que[200010];
long long Dp[200010][3];
bool instack[200010],mark[200010];
bool comp(const int &x,const int &y) {return in[x] < in[y];}
bool check(int x,int y) {return in[x] <= in[y] && out[x] >= out[y];}
void add(int x,int y) {
	edge[ ++ sum].to = y;
	edge[sum].next = fir[x];
	fir[x] = sum;
}
void inser(int x,int y,int z) {
	bian[ ++ size].to = y;
	bian[size].next = first[x];
	first[x] = size;
	bian[size].len = z;
}
void dfs(int x,int depth,int Anc) {
	dep[x] = depth;
	f[x][0] = Anc;
	in[x] = ++ tim;
	for(int i = 1;i <= 20;i ++) 
	    f[x][i] = f[f[x][i - 1]][i - 1];
	for(int u = fir[x];u;u = edge[u].next) 
	    if(dep[edge[u].to] == 0)
	        dfs(edge[u].to,depth + 1,x);
	out[x] = ++ tim;
} 
int lca(int x,int y) {
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = 20;i >= 0;i --) 
		if(dep[f[x][i]] >= dep[y]) 
			x = f[x][i];
	if(x == y) return x;
	for(int i = 20;i >= 0;i --) 
	    if(f[x][i] != f[y][i])
	        x = f[x][i],y = f[y][i];
	return f[x][0];
}
void dp(int x) {
	for(int u = first[x];u;u = bian[u].next) 
	    if(instack[bian[u].to])
	        dp(bian[u].to);
	if(mark[x] == false) {
		long long s1 = 0,s2 = 0;
		long long minx = 2 * inf;
		for(int u = first[x];u;u = bian[u].next) 
		    if(instack[bian[u].to])
		    {
		    	long long m1 = min(Dp[bian[u].to][0],Dp[bian[u].to][1]);
		    	long long m2;
		    	if(bian[u].len > 1) 
		    	    m2 = min(Dp[bian[u].to][0],Dp[bian[u].to][1] + 1);
		    	else m2 = min(Dp[bian[u].to][0],inf);
		    	s1 += m1;
		    	s2 += m2;
		    	minx = min(minx,Dp[bian[u].to][1] - m2);
		    }
		Dp[x][0] = min(s1 + 1,s2);
		Dp[x][1] = min(inf,s2 + minx);
	}
	if(mark[x] == true) {
		long long s = 0;
		Dp[x][0] = inf;
		for(int u = first[x];u;u = bian[u].next)
		    if(instack[bian[u].to])
		    {
		    	long long c;
		    	if(bian[u].len > 1) c = Dp[bian[u].to][1] + 1;
				else c = inf;
				s += min(c,Dp[bian[u].to][0]); 
		    }
		if(s >= inf) s = inf;
		Dp[x][1] = s;
		return ;
	}
}
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n - 1;i ++) {
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,1,1);
	scanf("%d",&Q);
	while(Q --) {
		scanf("%d",&m);len = m;top = 0;root = 0;
		for(int i = 1;i <= m;i ++) scanf("%d",&list[i]),que[i] = list[i];
		sort(list + 1,list + m + 1,comp);
		for(int i = 1;i < m;i ++) 
		    list[++ len] = lca(list[i],list[i + 1]);
		sort(list + 1,list + len + 1,comp);
		len = unique(list + 1,list + len + 1) - list - 1;
		for(int i = 1;i <= len;i ++) {
			while(top > 0 && !check(stack[top],list[i]))
			    top --;
			if(stack[top] == 0) root = list[i];
			else {
				int s = stack[top],t = list[i];
				inser(s,t,dep[t] - dep[s]);
			}
			stack[ ++ top] = list[i];
		}
		for(int i = 1;i <= len;i ++) instack[list[i]] = true;
		for(int i = 1;i <= m;i ++) mark[que[i]] = true;
		dp(root);
		for(int i = 1;i <= len;i ++) instack[list[i]] = false;
		for(int i = 1;i <= m;i ++) mark[que[i]] = false;
		for(int i = 1;i <= len;i ++) first[list[i]] = 0;size = 0;
		if(Dp[root][1] >= inf && Dp[root][0] >=inf) printf("-1
");
		else printf("%I64d
",min(Dp[root][1],Dp[root][0]));
	}
	return 0;
}