「Luogu4103」[HEOI2014]大工程

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

problem

Solution

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

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

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

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

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

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

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

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

Code

#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]]>=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;
}

「Luogu4103」[HEOI2014]大工程

原文：https://www.cnblogs.com/lizbaka/p/10660130.html