BZOJ2286: [Sdoi2011]消耗战 LCA单调性+树形dp
思路:
首先对于一次询问进行一次朴素的树形dp极为容易.不过这样需要O(n)的时间复杂度,这样总的时间复杂度为O(qn),无法通过.
我们能否对于一次询问,将时间复杂度限定至仅与关键点数有关呢?
我们考虑构造一个树结构,仅仅将关键点连接起来,并适当添加部分非关键点,我们如果在这样减缩后的树上做dp,就能使得复杂度只与关键点数有关.
我们利用一个单调栈维护树上的一条深度单调递增的链,当我们要添加的点与栈顶的点的lca深度小于栈顶时,我们不断弹栈并在这个过程中顺便维护此时树的形态.
容易发现,对于每次添加,至多在新树上添加一个点,因此新树的点数只与关键点线性相关.
接下来在新树上作朴素的树形dp就行了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #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 250010int 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;} |
评论 (0)