[bzoj2286][Sdoi 2011]消耗战

[bzoj2286]消耗战

标签：虚树 DP

题解

很容易找出(O(mn))的做法。
只需要每次都dp一遍。
但是m和n是同阶的，所以这样肯定会T的。

注意到dp的时候有很多节点是不需要的，真正有用的只是被询问的那k个点和他们的lca。
所以对于每次询问，我们只需要对于其中的点建一颗虚树。
然后在虚数上面dp。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
#define EREP_g(i,a) for(int i=start_g[(a)];i;i=g[i].next)
inline int read()
{
    int sum=0,p=1;char ch=getchar();
    while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
    if(ch=='-')p=-1,ch=getchar();
    while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum*p;
}
 
const int maxn=250020;
 
struct node {
    int v,next;ll w;
};
 
struct Node {
    int v,next;
};
 
const ll inf=1ll<<60;
node e[maxn*2];Node g[maxn*2];
int cnt,start[maxn],cnt_g,start_g[maxn];
 
inline void addedge(int u,int v,ll w)
{
    e[++cnt]=(node){v,start[u],w};
    start[u]=cnt;
}
 
inline void addedge_g(int u,int v)
{
    g[++cnt_g]=(Node){v,start_g[u]};
    start_g[u]=cnt_g;
}
 
int n,dfn[maxn],times,deep[maxn],p[maxn][20];
ll dp[maxn],val[maxn];
 
inline void dfs(int u,int fa)
{
    dfn[u]=++times;
    deep[u]=deep[fa]+1;
    p[u][0]=fa;
    EREP(i,u)
    {
        int v=e[i].v;
        if(v==fa)continue;
        val[v]=min(val[u],e[i].w);
        dfs(v,u);
    }
         
}
 
inline void pre_LCA()
{
    for(int j=1;(1<<j)<=n;j++)
        REP(i,1,n)p[i][j]=p[p[i][j-1]][j-1];
}
 
inline int lca(int u,int v)
{
    if(deep[u]<deep[v])swap(u,v);
    DREP(i,19,0)if(deep[p[u][i]]>=deep[v])u=p[u][i];
    if(u==v)return v;
    DREP(i,19,0)if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];
    return p[u][0];
}
 
inline void init()
{
    n=read();
    REP(i,1,n-1)
    {
        int u=read(),v=read();ll W;scanf("%lld",&W);
        addedge(u,v,W);
        addedge(v,u,W);
        //w[v]=W;
    }
    val[1]=inf;
    dfs(1,0);
    pre_LCA();
}
 
inline bool cmp(const int a,const int b)
{
    return dfn[a]<dfn[b];
}
 
inline void Dp(int u,int fa)
{
    ll res=0;dp[u]=val[u];
    EREP_g(i,u)
    {
        int v=g[i].v;
        if(v==fa)continue;
        Dp(v,u);
        res+=dp[v];
    }
    start_g[u]=0;
    if(res)dp[u]=min(res,dp[u]);
}
 
int add[maxn],st[maxn];
inline void doing()
{
    REP(i,1,read())
    {
        int top=0,tot=1;
        int k=read();
        REP(j,1,k)add[j]=read();
        cnt_g=0;//REP(j,1,2*k)start_g[j]=0;
        sort(add+1,add+k+1,cmp);
        REP(i,2,k)if(lca(add[tot],add[i])!=add[tot])add[++tot]=add[i];
        st[++top]=1;k=tot;      
        REP(j,1,k)
        {
            int u=st[top],v=add[j],Lca=lca(u,v);
            if(u!=Lca)
            {
                //int x=st[--top];
                while(dfn[st[--top]]>dfn[Lca])addedge_g(st[top],st[top+1]),addedge_g(st[top+1],st[top]);
 
                addedge_g(Lca,st[top+1]);addedge_g(st[top+1],Lca);
                if(Lca!=st[top])st[++top]=Lca;
            }
            st[++top]=v;
        }
        --top;
        while(top)addedge_g(st[top],st[top+1]),addedge_g(st[top+1],st[top]),top--;
        Dp(1,0);
        printf("%lld
",dp[1]);
    }
}
 
int main()
{
    init();
    doing();
    return 0;
}