3611: [Heoi2014]大工程

3611: [Heoi2014]大工程

链接

分析:

  树形dp+虚树。

  首先建立虚树,在虚树上dp。

  dp:sum[i]为i的子树中所有询问点之间的和。siz[i]为i的子树中有多少询问点,mn[i]为i的子树中询问点到根的最小距离,mx为i的子树中询问点到根的最大距离。

  具体过程见 https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-p4103

  

代码:

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream> using namespace std; const int N = ;
const int INF = 1e9; int head[N<<],to[N<<],nxt[N<<];
int siz[N],deth[N],fa[N],son[N],dfn[N],bel[N],sk[N],tag[N];
int mn[N],mx[N],val[N],A[N];
long long sum[N],Sum;
int Time_index,Min,Max,TotE,top; inline int read() {
int x = ,f = ;char ch = getchar();
for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;
for (; isdigit(ch); ch=getchar()) x=x*+ch-'';
return x * f;
}
bool cmp_dfn(const int &a,const int &b) {
return dfn[a] < dfn[b];
}
void Add_edge(int u,int v) {
++TotE; to[TotE] = v; nxt[TotE] = head[u]; head[u] = TotE;
++TotE; to[TotE] = u; nxt[TotE] = head[v]; head[v] = TotE;
}
void add_edge(int u,int v) {
++TotE; to[TotE] = v; val[TotE] = deth[v]-deth[u]; nxt[TotE] = head[u]; head[u] = TotE;
}
void dfs1(int u) {
siz[u] = ;
deth[u] = deth[fa[u]] + ; // 1的深度设为1。
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
if (v==fa[u]) continue;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs2(int u,int top) {
bel[u] = top;
dfn[u] = ++Time_index;
if (!son[u]) return ;
dfs2(son[u],top);
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
if (v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
int Lca(int u,int v) {
while (bel[u] != bel[v]) {
if (deth[bel[u]] < deth[bel[v]]) swap(u,v);
u = fa[bel[u]];
}
if (deth[u] < deth[v]) return u;
return v;
}
void Insert(int p) {
int x = sk[top];
if (x==) {sk[++top] = p; return;}
int lca = Lca(x,p);
while (lca != x) {
int y = sk[--top];
if (dfn[y] < dfn[lca]) {
add_edge(lca,x);sk[++top] = lca; // !!!
break;
}
add_edge(y,x);x = sk[top];
}
sk[++top] = p;
}
void DP(int u) {
if (tag[u]) mx[u] = mn[u] = ,sum[u] = ,siz[u] = ;
else mn[u] = INF,mx[u] = -INF,sum[u] = ,siz[u] = ;
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
DP(v);
Min = min(Min,mn[u]+mn[v]+val[i]); mn[u] = min(mn[u],mn[v]+val[i]);
Max = max(Max,mx[u]+mx[v]+val[i]); mx[u] = max(mx[u],mx[v]+val[i]);
Sum += 1ll*siz[u]*(sum[v]+val[i]*siz[v])+1ll*siz[v]*sum[u]; //!!!
sum[u] += sum[v]+val[i]*siz[v];
siz[u] += siz[v];
}
tag[u] = head[u] = ;
}
int main () { int n = read();
for (int i=; i<n; ++i) {
int u = read(),v = read();
Add_edge(u,v);
} dfs1();
dfs2(,); memset(head,,sizeof(head)); int m = read();
while (m--) {
TotE = ;top = ;sk[++top] = ; int k = read();
for (int i=; i<=k; ++i) A[i] = read(),tag[A[i]] = true;
sort(A+,A+k+,cmp_dfn); if (A[] != ) sk[++top] = A[]; // 防止1加入两边。
for (int i=; i<=k; ++i) Insert(A[i]);
while (--top) add_edge(sk[top],sk[top+]); Sum = ,Min = INF,Max = -INF;
DP();
printf("%lld %d %d\n",Sum,Min,Max);
} return ;
}
上一篇:【BZOJ3611】大工程(虚树,动态规划)


下一篇:maven跳过单元测试