BZOJ2286: [Sdoi2011]消耗战 LCA单调性+树形dp

思路:

首先对于一次询问进行一次朴素的树形dp极为容易.不过这样需要\(O(n)\)的时间复杂度,这样总的时间复杂度为\(O(qn)\),无法通过.

我们能否对于一次询问,将时间复杂度限定至仅与关键点数有关呢?

我们考虑构造一个树结构,仅仅将关键点连接起来,并适当添加部分非关键点,我们如果在这样减缩后的树上做dp,就能使得复杂度只与关键点数有关.

我们利用一个单调栈维护树上的一条深度单调递增的链,当我们要添加的点与栈顶的点的lca深度小于栈顶时,我们不断弹栈并在这个过程中顺便维护此时树的形态.

容易发现,对于每次添加,至多在新树上添加一个点,因此新树的点数只与关键点线性相关.

接下来在新树上作朴素的树形dp就行了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
    char buf[5000010],*o=buf;
    template<typename T>inline void print(T x){
        static int stk[100];int top=0;if(x<0)*o++='-',x=-x;
        if(!x)*o++=48;else{for(;x;x/=10)stk[++top]=x%10;for(int i=top;i>=1;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 250010
int head[N],next[N<<1],end[N<<1],len[N<<1];
inline void addedge(int a,int b,int x){
    static int q=1;end[q]=b,next[q]=head[a],len[q]=x,head[a]=q++;
}
inline void make(int a,int b,int x){addedge(a,b,x),addedge(b,a,x);}
 
int pa[N][21],w[N][21],dfn[N],id,dep[N];
void dfs(int x,int fa){
    dfn[x]=++id;
    for(int j=head[x];j;j=next[j])if(end[j]!=fa){
        dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,w[end[j]][0]=len[j],dfs(end[j],x);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
long long calc(int son,int Anc){
    int res=100010;for(int i=20;i>=0;--i)if(dep[pa[son][i]]>=dep[Anc])res=min(res,w[son][i]),son=pa[son][i];return res;
}
 
int seq[N],siz;
 
inline bool cmp(const int&a,const int&b){return dfn[a]<dfn[b];}
 
int stk[N],top,Anc[N];
 
struct Array{
    long long sum[N];int t[N];
    inline void modify(int x,int add,int v){
        if(t[x]!=v)t[x]=v,sum[x]=0;sum[x]+=add;
    }
    inline long long ask(int x,int v){
        if(t[x]!=v)t[x]=v,sum[x]=0;return sum[x];
    }
}f,IsImp;int nowv;
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    using namespace Fio;
    int n;Fio::Get(n);
    register int i,j;int a,b,x;for(i=1;i<n;++i)Get(a),Get(b),Get(x),make(a,b,x);
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1],w[i][j]=min(w[i][j-1],w[pa[i][j-1]][j-1]);
    int Q;Get(Q);
    while(Q--){
        Get(siz);for(i=1;i<=siz;++i)Get(seq[i]);++nowv;for(i=1;i<=siz;++i)IsImp.modify(seq[i],1,nowv);seq[++siz]=1;
        sort(seq+1,seq+siz+1,cmp);int end=siz;
        for(top=0,i=1;i<=siz;++i){
            if(!top)stk[++top]=seq[i];
            else{
                int Lca=lca(stk[top],seq[i]);Anc[seq[i]]=Lca;
                while(dep[stk[top]]>dep[Lca]){if(dep[stk[top-1]]<=dep[Lca])Anc[stk[top]]=Lca;--top;}
                if(stk[top]!=Lca)Anc[Lca]=stk[top],seq[++end]=stk[++top]=Lca;
                stk[++top]=seq[i];
            }
        }
        sort(seq+1,seq+end+1,cmp);
        //for(i=1;i<=siz;++i)printf("%d ",seq[i]);puts("");
        long long dis;
        for(i=end;i>=1;--i){
            dis=calc(seq[i],Anc[seq[i]]);
            if(IsImp.ask(seq[i],nowv))f.modify(Anc[seq[i]],dis,nowv);else f.modify(Anc[seq[i]],min(dis,f.ask(seq[i],nowv)),nowv);
        }
        print(f.ask(1,nowv));
    }
    return Final(),0;
}