NC20546. [HEOI2014]大工程
描述
输入描述
第一行 n 表示点数。
接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。点从 1 开始标号。
接下来一行 q 表示计划数。
对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
输出描述
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
示例1
输入:
10 2 1 3 2 4 1 5 2 6 4 7 5 8 6 9 7 10 9 5 2 5 4 2 10 4 2 5 2 2 6 1 2 6 1
输出:
3 3 3 6 6 6 1 1 1 2 2 2 2 2 2
C++14(g++5.4) 解法, 执行用时: 2149ms, 内存消耗: 147172K, 提交时间: 2019-08-26 21:19:27
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV=1e6+5,MAXE=2*MAXV,DEP=21,INF=0x7f7f7f7f;
int V,maxi,mini;
vector<int> query;
bool tag[MAXV];
ll sum;
namespace T
{
struct Edge
{
int to, last;
void set(int _to, int _last) { to = _to, last = _last; }
} es[MAXE];
int top, head[MAXV];
void init() { top = 0, fill(head + 1, head + V + 1, -1); }
void add(int fr, int to)
{
es[top].set(to, head[fr]);
head[fr] = top++;
}
int fa[MAXV][DEP],depth[MAXV],dfn[MAXV],dfs_num;
void build_lca(int fr)
{
dfn[fr]=++dfs_num;
for(int i=1;(1<<i)<=depth[fr];++i)
fa[fr][i]=fa[fa[fr][i-1]][i-1];
for(int i=head[fr],to;~i;i=es[i].last)
{
to=es[i].to;
if(to==fa[fr][0]) continue;
depth[to]=depth[fr]+1;
fa[to][0]=fr;
build_lca(to);
}
}
int lca(int a,int b)
{
if(depth[a]<depth[b]) swap(a,b);
for(int i=DEP-1;i>=0;--i)
if(depth[a]-(1<<i)>=depth[b])
a=fa[a][i];
if(a==b) return a;
for(int i=DEP-1;i>=0;--i)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
int S[MAXV];
void build_fake_tree()
{
sort(query.begin(),query.end(),
[](int a,int b){ return dfn[a]<dfn[b]; });
int t=top=0,father;
S[++t]=1,head[1]=-1;
for(int fr:query)
{
if(fr==1) continue;
if((father=lca(S[t],fr))!=S[t])
{
while(dfn[S[t-1]]>dfn[father]) add(S[t-1],S[t]),--t;
if(father!=S[t-1])
head[father]=-1,add(father,S[t]),S[t]=father;
else
add(S[t-1],S[t]),--t;
}
head[fr]=-1,S[++t]=fr;
}
while(t>1) add(S[t-1],S[t]),--t;
}
int sz[MAXV],mxd[MAXV],mnd[MAXV]; // 自己及下面的选中点,上面最近的选中点
void dfs(int fr)
{
sz[fr]=tag[fr],mxd[fr]=0,mnd[fr]=tag[fr]?0:INF;
int smxd=0,smnd=INF,d;
for(int i=head[fr],to;~i;i=es[i].last)
{
to=es[i].to;
dfs(to);
sz[fr]+=sz[to];
sum+=(depth[to]-depth[fr])*(ll)sz[to]*(query.size()-sz[to]);
d=mxd[to]+depth[to]-depth[fr];
if(d>mxd[fr]) smxd=mxd[fr],mxd[fr]=d;
else if(d>=smxd) smxd=d;
d=mnd[to]+depth[to]-depth[fr];
if(d<mnd[fr]) smnd=mnd[fr],mnd[fr]=d;
else if(d<=smnd) smnd=d;
}
if(smxd||tag[fr]) maxi=max(maxi,mxd[fr]+smxd);
mini=min(mini,mnd[fr]+smnd);
}
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int q,k,x;
scanf("%d",&V);
T::init();
for(int i=1,fr,to;i<V;++i)
{
scanf("%d %d",&fr,&to);
T::add(fr,to),T::add(to,fr);
}
T::build_lca(1);
scanf("%d",&q);
for(int i=0;i<q;++i)
{
scanf("%d",&k);
query=vector<int>();
sum=maxi=0,mini=INF;
for(int j=0;j<k;++j)
{
scanf("%d",&x);
query.push_back(x),tag[x]=1;
}
T::build_fake_tree();
T::dfs(1);
printf("%lld %d %d\n",sum,mini,maxi);
for(int j:query) tag[j]=0;
}
return 0;
}
/*==================================================================
added at 2019-08-26 21:12:27 P4103
虚树上维护关键点之间距离和\距离最大值\最小值
关键点:
1. maxi和mini这两个答案都需要记录最大/小和次大/小来进行维护
2. 1不作为关键点的情况对求最大值有影响需要特判
==================================================================*/
C++(g++ 7.5.0) 解法, 执行用时: 445ms, 内存消耗: 128232K, 提交时间: 2022-08-08 20:36:11
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 1e6 + 5;
struct Graph { int to, next; } e[MAX_N << 2];
int fir1[MAX_N], fir2[MAX_N], e_cnt;
void clearGraph() {
memset(fir1, -1, sizeof(fir1));
memset(fir2, -1, sizeof(fir2));
}
void Add_Edge(int *fir, int u, int v) {
e[e_cnt] = (Graph){v, fir[u]};
fir[u] = e_cnt++;
}
namespace Tree {
int fa[MAX_N], dep[MAX_N], size[MAX_N], top[MAX_N], son[MAX_N], dfn[MAX_N], tim;
void dfs1(int x) {
dfn[x] = ++tim;
size[x] = 1, dep[x] = dep[fa[x]] + 1;
for (int i = fir1[x]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa[x]) continue;
fa[v] = x; dfs1(v); size[x] += size[v];
if (size[v] > size[son[x]]) son[x] = v;
}
}
void dfs2(int x, int tp) {
top[x] = tp;
if (son[x]) dfs2(son[x], tp);
for (int i = fir1[x]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa[x] || v == son[x]) continue;
dfs2(v, v);
}
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
}
using Tree::LCA; using Tree::dfn; using Tree::dep;
int N, M, K, a[MAX_N];
bool key[MAX_N];
int f[MAX_N], g[MAX_N], s[MAX_N];
bool cmp(int i, int j) { return dfn[i] < dfn[j]; }
void build() {
static int stk[MAX_N], top;
sort(&a[1], &a[K + 1], cmp);
stk[top = 1] = 1; fir2[1] = -1;
e_cnt = 0;
for (int i = 1; i <= K; i++) {
key[a[i]] = 1;
if (a[i] == 1) continue;
int lca = LCA(stk[top], a[i]);
if (lca != stk[top]) {
while (dfn[lca] < dfn[stk[top - 1]]) {
int u = stk[top], v = stk[top - 1];
Add_Edge(fir2, u, v), Add_Edge(fir2, v, u);
--top;
}
if (dfn[lca] > dfn[stk[top - 1]]) {
fir2[lca] = -1; int u = stk[top], v = lca;
Add_Edge(fir2, u, v), Add_Edge(fir2, v, u);
stk[top] = lca;
}
else {
int u = lca, v = stk[top--];
Add_Edge(fir2, u, v), Add_Edge(fir2, v, u);
}
}
fir2[a[i]] = -1, stk[++top] = a[i];
}
for (int i = 1; i < top; i++) {
int u = stk[i], v = stk[i + 1];
Add_Edge(fir2, u, v), Add_Edge(fir2, v, u);
}
}
long long ans1;
int ans2, ans3;
void Dp(int x, int fa) {
s[x] = key[x], f[x] = 0, g[x] = (key[x] ? 0 : 1e9);
for (int i = fir2[x]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
Dp(v, x);
}
for (int i = fir2[x]; ~i; i = e[i].next) {
int v = e[i].to, w = dep[v] - dep[x];
if (v == fa) continue;
ans1 += 1ll * (K - s[v]) * s[v] * w;
if (s[x] > 0) {
ans2 = min(ans2, g[x] + w + g[v]);
ans3 = max(ans3, f[x] + w + f[v]);
}
g[x] = min(g[x], g[v] + w);
f[x] = max(f[x], f[v] + w);
s[x] += s[v];
}
key[x] = 0;
}
int main () {
#ifndef ONLINE_JUDGE
#endif
clearGraph();
N = gi();
for (int i = 1; i < N; i++) {
int u = gi(), v = gi();
Add_Edge(fir1, u, v), Add_Edge(fir1, v, u);
}
Tree::dfs1(1), Tree::dfs2(1, 1);
M = gi();
while (M--) {
ans1 = 0, ans2 = 1e9, ans3 = 0;
K = gi(); for (int i = 1; i <= K; i++) a[i] = gi();
build();
Dp(1, 0);
printf("%lld %d %d\n", ans1, ans2, ans3);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1426ms, 内存消耗: 177576K, 提交时间: 2020-08-10 10:40:39
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int nn=1e6+1,INMA=1e8;
int n,q,ti,tp,node[nn];
int dfn[nn],dep[nn],fa[nn][20];
int minn,maxn,mi[nn],ma[nn],size[nn];
long long sumn,sum[nn];
bitset<nn>key;
stack<int>st;
vector<int>son[nn];
void add(int i){
mi[i]=key[i]?0:INMA;
ma[i]=key[i]?0:-INMA;
size[i]=key[i],sum[i]=0;
st.push(i);
}void dfs(int u){
int v;dfn[u]=++ti;
for(int i=0;i<20&&fa[u][i];i++)
fa[u][i+1]=fa[fa[u][i]][i];
for(unsigned int i=0;i<son[u].size();i++)
if(!dfn[v=son[u][i]])
dep[v]=dep[fa[v][0]=u]+1,dfs(v);
}void update(int u,int v){
if(!v)return ;
int w=dep[v]-dep[u];
sumn+=size[u]*(sum[v]+size[v]*w)+size[v]*sum[u];
size[u]+=size[v],sum[u]+=sum[v]+size[v]*w;
minn=min(minn,mi[u]+mi[v]+w),mi[u]=min(mi[u],mi[v]+w);
maxn=max(maxn,ma[u]+ma[v]+w),ma[u]=max(ma[u],ma[v]+w);
}bool cmp(int a,int b){return dfn[a]<dfn[b];}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
int d=dep[a]-dep[b];
for(int i=19;i>=0;i--)
if(d>=1<<i)
d-=1<<i,a=fa[a][i];
if(a==b)return a;
for(int i=19;i>=0;i--)
if(fa[a][i]!=fa[b][i])
a=fa[a][i],b=fa[b][i];
return fa[a][0];
}int main(){
scanf("%d",&n);
for(int i=1,a,b;i<n;i++){
scanf("%d%d",&a,&b);
son[a].pb(b),son[b].pb(a);
}dfs(node[0]=1);
scanf("%d",&q);
for(int k,nod;q--;){
sumn=0,minn=INMA,maxn=-INMA;
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d",node+i);
key[node[i]]=true;
}sort(node+1,node+k+1,cmp),add(1);
for(int i=1;i<=k;i++)
if(node[i]!=1){
nod=lca(node[i],node[i-1]);
for(tp=0;dep[nod]<dep[st.top()];tp=st.top(),st.pop())
update(st.top(),tp);
if(nod!=st.top())add(nod);
update(nod,tp),add(node[i]);
}
for(tp=0;!st.empty();tp=st.top(),st.pop())
update(st.top(),tp);
printf("%lld %d %d\n",sumn,minn,maxn);
for(int i=1;i<=k;i++)
key[node[i]]=false;
}return 0;
}