锐客网

  1. 首页 > it技术 > >

online|bzoj2286: [Sdoi2011消耗战

动态规划数据结构其他bzoj树形dponlinejudge构造dfs序

链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2286
题意：中文题。
分析：题目中要求所有的关键点与根1断开，很容易想到树形dp。但是由于多组询问会导致时间*m。单次O(n)不可取。很显然是要优化的，我们发现单次O(n)时还是会做很多无用功，而且题目说sigma(ki)<=5*10^5，意思是所有查询的点最多才涉及5*10^5个点。于是有了一种虚树的方法：我们构造一棵包含当前询问中所有关键点的树。构造方法：先按dfs序将所有关键点排序，先处理掉包含关系的点（有包含关系那么显然只要断开与根最近点的就够了），再用一个栈维护一条原树上的链，当加入新点的时候我们判断栈顶节点d[top]和新节点h[i]的lca在这条链中的位置，因为lca包含d[top]而且维护的是一条链，那么lca必定是d[top]到根路径上的点（不一定在栈内），我们在踢出栈顶元素的时候只要给栈顶元素与lca之间加一条边即可（因为可能存在情况是a,b两点断开的位置都是在lca(a,b)到根上的点，如果不加入lca这个点那么断点花费就会花双倍）。这样处理完之后新树的节点最多为2*K。然后树上dp即可。O(k*logn)
代码：

#include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=250100; const int MAX=100000000; const int mod=100000000; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=998244353; const ll INF=10000000010; typedef double db; typedef unsigned long long ull; int tot,u[N],v[2*N],w[2*N],pre[2*N]; void add(int x,int y,int z) { if (x==y) return ; v[tot]=y; w[tot]=z; pre[tot]=u[x]; u[x]=tot++; } int k,de[N],in[N],f[N][20],out[N],dis[N]; void dfs(int x,int y,int z) { k++; in[x]=k; f[x][0]=y; de[x]=de[y]+1; dis[x]=min(z,dis[y]); for (int i=1; i<20; i++) if (de[x]>(1<=out[y]; } ll dp[N]; int getlca(int x,int y) { if (de[x]=0; i--) if (de[x]-(1<=de[y]) x=f[x][i]; if (x==y) return x; for (int i=20; i>=0; i--) if (de[x]>(1<=de[d[k-1]]) { add(lca,d[k],dis[d[k]]); k--; if (d[k]!=lca) d[++k]=lca; break ; } add(d[k-1],d[k],dis[d[k]]); k--; } if (d[k]!=h[i]) d[++k]=h[i]; } while (--k) add(d[k],d[k+1],dis[d[k+1]]); getans(1,0); printf("%lld\n", dp[1]); } int main() { int i,n,m,x,y,z; scanf("%d", &n); tot=0; memset(u,-1,sizeof(u)); for (i=1; i



    推荐阅读


    上一篇：AndroidStudio 中使用Xutils3注解

    下一篇：————数学————|扩展欧几里得定理 新手向证明及代码