消耗战

https://ac.nowcoder.com/acm/problem/212521

前言

写这篇题解主要是复习一下
可能会写的比较省略

算法

虚树+倍增+动态规划

引入

看到这道题我们立马可以想到一个DP方程
我们设DP[i]表示使 $i$ 与其子树中的所有关键点分开的最小代价
对于一个节点 $u$
以及他的儿子 $v$

若 $v$ 是关键点，那么DP[u]+=W(u,v)
若 $v$ 不是关键点，那么DP[u]+=min{DP[v],W(u,v)}

但我们发现这是一个 $O(q \cdot n)$ 的暴力！
但我们认真观察数据范围，发现

$\sum k_i \leq 5 \times 10^5$

所以我们非常希望能够把时间复杂度的有关因素转移到 $k_i$ 上去
这时候我们就需要引入虚树的概念了

简介

对于虚树，主要是处理当问题中无用信息非常多时，简化问题的一种思想
对于样例的第2个询问
Newcoder题解-1.png
我们发现，有用的其实就只有 $3,5,7,8$ 这几个点
即：我们在转移的时候真正对结果有影响的点其实非常少
所以我们考虑有用的点是那些
Newcoder题解-2.png
发现我们其实可以直接把一棵树浓缩为RT2的结构
那么在这棵树上DP就可以省下许多时间了

建树

对于建树，我们就需要使用到栈了
我们可以用栈维护一条链
即RT2的 $1 \rightarrow 5 \rightarrow 7 \rightarrow 8$

步骤一：将关键点按DFS序排序
步骤二：插入1节点作为虚树的根节点
步骤三：循环关键点数组，求出Stack[Top]和Key[1]的LCA
步骤四：判断

$\Rightarrow$
若Dep[Stack[Top-1]] $>$ Dep[LCA]，这个节点一定在此链上，那么我们将此节点加入到栈顶
若Dep[Stack[Top-1]] $>$ Dep[LCA]，这个节点不在当前链上，循环直到Dep[Stack[Top-1]] $\leq$ Dep[LCA]

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Rightarrow$ 若Stack[Top-1]!=LCA那么，我们将Stack[Top]弹出，加入LCA,连LCA $\rightarrow$ Stack[Top]的边

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ 若Stack[Top-1]==LCA那么我们直接弹出Stack[Top]连Stack[Top-1]到Stack[Top]的边

步骤五：加入Key[i]节点到栈中
步骤六：回到步骤三知道将所有的关键点插入完截至

后续

接下来我们需要处理新边的权值问题
我们观察DP转移式，发现对于相邻两个在虚树上的点
我们只需要记录这两个点在原树上路径上的最小权值即可
这时候我们就需要使用到倍增了
时间复杂度： $O(k \log k)$

注意事项

由于我们的询问是 $q \leq 5 \times 10^5$
所以我们不能直接每次都清空所有数组
对于链式前向星的数组
我们可以在每次重新使用此点时，将Head[]设为0
对于栈我们也需要每次直接Top=1即可
还有一些注意事项，大家可以自己琢磨一下，很有意义

代码

//P2495
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f3f3f3f3f
#define Skip cout<<endl
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=5e5+10;

LL Total,u,v,w;
LL Next[MaxN<<1],Head[MaxN],End[MaxN<<1],Val[MaxN],Cur;
LL NNext[MaxN<<1],HHead[MaxN],EEnd[MaxN<<1],CCur,VVal[MaxN<<1];
LL Dfn[MaxN],dfn_num;
LL Test,Tot,Key[MaxN],Tag[MaxN],LT,NT;
LL Stack[MaxN],Top;
LL Anc[MaxN][21],Dep[MaxN],Min[MaxN][21];
LL DP[MaxN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void DFS(LL New,LL Pre) {
    Dfn[New]=++dfn_num;
    Dep[New]=Dep[Pre]+1;
    FOR(i,1,20) {
        Anc[New][i]=Anc[Anc[New][i-1]][i-1];
        Min[New][i]=min(Min[New][i-1],Min[Anc[New][i-1]][i-1]);
    }
    for(LL i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        Anc[End[i]][0]=New;
        Min[End[i]][0]=Val[i];
        DFS(End[i],New);
    }
}

inline LL Get(LL X,LL Y) {
    if(Dep[X]<Dep[Y]) swap(X,Y);
    BOR(i,20,0) { if(Dep[Anc[X][i]]>=Dep[Y]) X=Anc[X][i]; }
    if(X==Y) return X;
    BOR(i,20,0) { if(Anc[X][i]!=Anc[Y][i]) X=Anc[X][i],Y=Anc[Y][i]; }
    return Anc[X][0];
}

inline LL Catch(LL X,LL Y) {
    if(Dep[X]<Dep[Y]) swap(X,Y);
    LL Res=INF;
    BOR(i,20,0) { if(Dep[Anc[X][i]]>=Dep[Y]) Res=min(Res,Min[X][i]),X=Anc[X][i]; }
    return Res;
}

inline bool Comp(LL A,LL B) { return Dfn[A]<Dfn[B]; }
inline void Add_Edge(LL From,LL To,LL Temp) { Next[++Cur]=Head[From]; Head[From]=Cur; End[Cur]=To; Val[Cur]=Temp; }
inline void Re_Add_Edge(LL From,LL To) { NNext[++CCur]=HHead[From]; HHead[From]=CCur; EEnd[CCur]=To; VVal[CCur]=Catch(From,To); }
inline void Build() {
    sort(Key+1,Key+Tot+1,Comp);
    // Skip;
    // FOR(i,1,Tot) cout<<Key[i]<<" ";
    // Skip;
    HHead[1]=0; 
    Stack[Top=1]=1;
    FOR(i,1,Tot) {
        if(Key[i]==1) continue;
        LL LCA=Get(Stack[Top],Key[i]);
        if(LCA!=Stack[Top]) {
            while(Dfn[Stack[Top-1]]>Dfn[LCA]) { Re_Add_Edge(Stack[Top-1],Stack[Top]); Top--; }
            if(Dfn[Stack[Top-1]]!=Dfn[LCA]) { HHead[LCA]=0; Re_Add_Edge(LCA,Stack[Top]); Stack[Top]=LCA; }
            else { Re_Add_Edge(Stack[Top-1],Stack[Top]); Top--; }
        }
        HHead[Key[i]]=0;
        Stack[++Top]=Key[i];
    }
    FOR(i,1,Top-1) Re_Add_Edge(Stack[i],Stack[i+1]); 
}

inline void Solve(LL New,LL Pre) {
    DP[New]=0;
    // Skip;
    // cout<<New<<" "<<Pre<<endl;
    // Skip;
    for(LL i=HHead[New];i;i=NNext[i]) {
        if(EEnd[i]==Pre) continue;
        Solve(EEnd[i],New);
        if(Tag[EEnd[i]]<=NT && Tag[EEnd[i]]>LT) DP[New]+=VVal[i];
        else DP[New]+=min(VVal[i],DP[EEnd[i]]);
    }
}

inline LL Read() {
    LL Temp=0;
    char Ch=getchar();
    while(Ch>'9' || Ch<'0') Ch=getchar();
    while(Ch>='0' && Ch<='9') Temp=(Temp<<1)+(Temp<<3)+(Ch ^ 48),Ch=getchar();
    return Temp;
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    Total=Read();
    FOR(i,1,Total-1) { u=Read(); v=Read(); w=Read(); Add_Edge(u,v,w); Add_Edge(v,u,w); }
    DFS(1,0);
    // cout<<endl;
    // FOR(i,1,Total) cout<<Min[i]<<" ";
    // cout<<endl;
    Test=Read();
    while(Test--) {
        Tot=Read();
        LT=NT;
        FOR(i,1,Tot) { Key[i]=Read(); Tag[Key[i]]=++NT; }
        Build();
        Solve(1,0);
        cout<<DP[1]<<endl;
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}