Problem

https://www.luogu.org/problemnew/show/P4103

Solution

辣鸡 LCT/ 虚树毁我青春

本题集合了虚树所有该有的麻烦的要点
集合了所有树形 dp 该有的奇怪的 trick

第 2 / 3 小问，经过根和不经过根的 dp 分别讨论进行 dp
第 1 小问，先算出一个根再进行换根转移，最后除以二

同时要注意的是，哪些是询问点而哪些是 lca，lca 是不能统计的

然后一种方法是在右链维护的时候直接 dp
但是按照我这种方法我必须递归两遍所以这样的话绝对会很麻烦

另一种是建图递归
但是我 MLE 了 qaq

然后当我开始打算弃疗打右链维护的时候
我发现我建虚树的时候没退栈...

当时我是怎么 AC 三个点的？

Code

// Code by ajcxsu
// Problem: big project

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

ll ans1, ans2, ans3;
const int N=1e6+10, M=4e6+10;
int h[N], vt[N], to[M], nexp[M], W[M], p=1, bp;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
inline void vins(int a, int b, int w) {
    nexp[p]=vt[a], vt[a]=p, to[p]=b, W[p]=w, p++;
}

int dfn[N], son[N], dep[N], siz[N], fa[N];
int top[N], idx;
void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dep[to[u]]) {
            fa[to[u]]=x, dfs1(to[u], k+1);
            siz[x]+=siz[to[u]];
            if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
}
void dfs2(int x, int t) {
    top[x]=t, dfn[x]=++idx;
    if(son[x]) dfs2(son[x], t);
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) dfs2(to[u], to[u]);
}
int lca(int s, int t) {
    if(!s || !t) return 0;
    while(top[s]!=top[t]) {
        if(dep[top[s]]<dep[top[t]]) swap(s,t);
        s=fa[top[s]];
    }
    if(dep[s]>dep[t]) return t;
    return s;
}

int lis[N], ki;
bool t[N];
bool cmp(const int &a, const int &b) { return dfn[a]<dfn[b]; }
int stk[N], sz;

ll f[N], fs[N], f2[N], f2m[N], f3[N], f3m[N];
void dp1(int x) {
    f[x]=0, fs[x]=t[x], f2[x]=f2m[x]=0, f3[x]=f3m[x]=0x7fffffffffffll;
    ll a=0, b=0;
    ll c=0x7fffffffffffll, d=0x7fffffffffffll;
    if(t[x]) c=0;
    for(int u=vt[x];u;u=nexp[u]) {
        if(!x) W[u]=0;
        dp1(to[u]);
        fs[x]+=fs[to[u]];
        f[x]+=f[to[u]]+W[u]*fs[to[u]];
        if(f2m[to[u]]+W[u]>a) b=a, a=f2m[to[u]]+W[u];
        else if(f2m[to[u]]+W[u]>b) b=f2m[to[u]]+W[u];
        f2[x]=max(f2[to[u]], f2[x]);

        if(f3m[to[u]]+W[u]<c) d=c, c=f3m[to[u]]+W[u];
        else if(f3m[to[u]]+W[u]<d) d=f3m[to[u]]+W[u];
        f3[x]=min(f3[x], f3[to[u]]);
    }
    f2m[x]=a, f3m[x]=c;
    f2[x]=max(f2[x], a+b);
    f3[x]=min(f3[x], c+d);
}
void dp2(int x) {
    if(t[x]) ans1+=f[x];
    ll bak=f[x], bak2, bak3=fs[x], bak4;
    for(int u=vt[x];u;u=nexp[u]) {
        bak2=f[to[u]], bak4=fs[to[u]];
        f[x]-=f[to[u]]+W[u]*fs[to[u]];
        fs[x]-=fs[to[u]];
        fs[to[u]]=bak3;
        f[to[u]]+=f[x]+W[u]*fs[x];
        dp2(to[u]);
        f[x]=bak, f[to[u]]=bak2, fs[x]=bak3, fs[to[u]]=bak4;
    }
    vt[x]=0;
    t[x]=0;
}

void solve() {
    ans1=0;
    p=bp;
    sz=0;
    sort(lis, lis+ki, cmp);
    stk[++sz]=0;
    int d;
    for(int i=0;i<ki;i++) {
        d=lca(stk[sz], lis[i]);
        while(sz-1>0 && dep[stk[sz-1]]>=dep[d]) vins(stk[sz-1], stk[sz], dep[stk[sz]]-dep[stk[sz-1]]), sz--;
        if(stk[sz]!=d) vins(d, stk[sz], dep[stk[sz]]-dep[d]), stk[sz]=d;
        stk[++sz]=lis[i];
    }
    for(int i=1;i<sz;i++) vins(stk[i], stk[i+1], dep[stk[i+1]]-dep[stk[i]]);
    dp1(0);
    dp2(0);
    printf("%lld %lld %lld\n", ans1/2ll, f3[0], f2[0]);
}


int main() {
    int n;
    gn(n);
    int u,v;
    for(int i=1;i<n;i++)
        gn(u), gn(v), ins(u,v), ins(v,u);
    dfs1(1,1), dfs2(1,1);
    bp=p;
    int q;
    gn(q);
    while(q--) {
        gn(ki);
        for(int i=0;i<ki;i++) gn(lis[i]), t[lis[i]]=1;
        solve();
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4103.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆