「Luogu4103」[HEOI2014]大工程

调了一个晚上，我果然还是too young,too simpletoo\space young,too\space simple，还是要学习一个

problem

Solution

之前也写过一个虚树的题目是消耗战来着，不过那个题目有特殊性质，虚树不是普通虚树

Anyway按你胃，对于每次询问，我们首先还是建出虚树

建好虚树之后，对于第一问，我们可以通过计算每条边两端关键点的数量来得到这条边对答案的贡献

对于第二和第三问，设f[x]f[x]表示在以xx为根的子树中距离xx最近的关键点与xx的距离是多少,g[x]g[x]是最远的关键点

以f[x]f[x]为例，枚举每一个子节点，转移为：

ans2=min(ans2,f[x]+dis(x,y)+f[y])ans_2=min(ans_2,f[x]+dis(x,y)+f[y])

f[x]=min(f[x],f[y]+dis(x,y))f[x]=min(f[x],f[y]+dis(x,y))

注意需要先更新ansans再更新f/gf/g数组，f[x]/g[x]f[x]/g[x]第一次被更新前不能更新ansans

Code

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
169
170
171
172
173
174
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int inf=0x3f3f3f3f;
const int maxn=1000000+5;
int n,q,K;
int dfn[maxn],sign;
ll ans1;
int ans2,ans3;
int key[maxn],isk[maxn];
int f[maxn],g[maxn];

struct edge
{
	int u,v,w,nxt;
}e[maxn];

int prt[maxn][25],dep[maxn];
int head[maxn],ecnt;
void eADD(int u,int v,int w)
{
	e[++ecnt].u=u;
	e[ecnt].v=v;
	e[ecnt].w=w;
	e[ecnt].nxt=head[u];
	head[u]=ecnt;
}

void Pre(int u,int fa)
{
	dep[u]=dep[fa]+1;
	dfn[u]=++sign;
	prt[u][0]=fa;
	for(register int i=1;(1<<i)<=dep[u];++i)
		prt[u][i]=prt[prt[u][i-1]][i-1];
	for(register int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		Pre(v,u);
	}
}

int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(register int i=20;i>=0;--i)
		if(dep[prt[x][i]]&gt;=dep[y])
			x=prt[x][i];
	if(x==y)return x;
	for(register int i=20;i>=0;--i)
		if(prt[x][i]!=prt[y][i])
			x=prt[x][i],y=prt[y][i];
	return prt[x][0];
}

int siz[maxn];
void clear()
{
	for(register int i=1;i<=ecnt;++i)
	{
		head[e[i].u]=siz[e[i].u]=f[e[i].u]=g[e[i].u]=0;
		head[e[i].v]=siz[e[i].v]=f[e[i].v]=g[e[i].u]=0;
		e[i].u=e[i].v=e[i].w=e[i].nxt=0;
	}
	ecnt=0;
}

void dfs1(int u,int fa)
{
	f[u]=isk[u]?0:inf;
	g[u]=0;
	siz[u]=isk[u];
	for(register int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs1(v,u);
		ans1+=1ll*siz[v]*e[i].w*(K-siz[v]);
		if(siz[u])
		{
			ans2=min(ans2,f[u]+e[i].w+f[v]);
			ans3=max(ans3,g[u]+e[i].w+g[v]);
		}
		f[u]=min(f[u],f[v]+e[i].w);
		g[u]=max(g[u],g[v]+e[i].w);
		siz[u]+=siz[v];
	}
}

bool cmp(const int &a,const int &b)
{
	return dfn[a]<dfn[b];
}

int stk[maxn],top;
void Build()
{
	sort(key+1,key+K+1,cmp);
	stk[top=1]=key[1];
	for(register int i=2;i<=K;++i)
	{
		int lca=LCA(stk[top],key[i]);
		if(lca!=stk[top])
		{
			while(top>1 && dfn[lca]<=dfn[stk[top-1]])
			{
				eADD(stk[top-1],stk[top],dep[stk[top]]-dep[stk[top-1]]);
				eADD(stk[top],stk[top-1],dep[stk[top]]-dep[stk[top-1]]);
				--top;
			}
			if(lca!=stk[top])
			{
				eADD(stk[top],lca,dep[stk[top]]-dep[lca]);
				eADD(lca,stk[top],dep[stk[top]]-dep[lca]);
				stk[top]=lca;
			}
		}
		stk[++top]=key[i];
	}
	while(top>1)
	{
		eADD(stk[top-1],stk[top],dep[stk[top]]-dep[stk[top-1]]);
		eADD(stk[top],stk[top-1],dep[stk[top]]-dep[stk[top-1]]);
		--top;
	}
}

void Work()
{
	read(K);
	for(register int i=1;i<=K;++i)
		read(key[i]),isk[key[i]]=1;
	Build();
	ans1=ans3=0;
	ans2=inf;
	dfs1(key[1],0);
	printf("%lld %d %d\n",ans1,ans2,ans3);
	clear();
	for(register int i=1;i<=K;++i)isk[key[i]]=0;
}

int main()
{
	read(n);
	for(register int i=1;i<n;++i)
	{
		int u,v;
		read(u),read(v);
		eADD(u,v,1);
		eADD(v,u,1);
	}
	Pre(1,0);
	for(register int i=1;i<=n;++i)head[i]=0;
	for(register int i=1;i<=ecnt;++i)e[i].u=e[i].v=e[i].w=e[i].nxt=0;
	ecnt=0;
	read(q);
	while(q--)Work();
	return 0;
}