南京 网站建设 运营服务 骗子公司,品牌推广名词解释,用ps做网站导航,wordpress 带宽购物虚树是用来优化树形dp的东西#xff0c;它的转移是从一些特殊点#xff0c;向根节点转移#xff0c;期间它有用的转移点比较特殊。通常询问次数较多#xff0c;但特殊点总和较少#xff0c;就可以每次询问先建虚树再跑dp。单调栈建虚树 O ( k l o g n ) O(klogn) O(klogn)…虚树是用来优化树形dp的东西它的转移是从一些特殊点向根节点转移期间它有用的转移点比较特殊。通常询问次数较多但特殊点总和较少就可以每次询问先建虚树再跑dp。单调栈建虚树 O ( k l o g n ) O(klogn) O(klogn) k k k为特殊点数 n n n为原树上点数
虚树的点数为特殊点两倍
单调栈构造虚树强制根节点为1或者先加入dfs最小的特殊点便于统计答案
void build(){std::sort(a1,a1m,[](int i,int j){return dfn[i]dfn[j];});int top0;cnt0;stk[top]1;head[1]0;//顺便清空之前的虚树也可以直接遍历一遍虚树清除for (int i1;im;i){if (a[i]!1){//全程不用管top大小int lclca(stk[top],a[i]);if (lc!stk[top]){//当前节点已不再当前栈维护的链上while (dfn[lc]dfn[stk[top-1]]){//一直跳出并添加已经确定的边add(stk[top-1],stk[top],0);top--;}if (dfn[lc]dfn[stk[top-1]]){//lc之前没有加入到栈中head[lc]0;add(lc,stk[top--],0);stk[top]lc;}else{//lc加入过栈add(lc,stk[top--],0);}}//最后只要把a[i]加入该链head[a[i]]0;stk[top]a[i];}}for (int i1;itop;i){add(stk[i],stk[i1],0);//将链上的节点依次建边}
}P2495 [SDOI2011] 消耗战 正常的每次询问跑一边树形dp时间爆炸所以直接建虚树跑树形dp在原树上要维护一个点 x x x 到根节点的最小断边 f x f_x fx。转移直接分情况 当前点为特殊点必须将 u u u分离出来 d p u f u dp_uf_u dpufu 当前点不为特殊点可以将 u u u直接分离或者让 u u u从其已经分离的子树分离 d p u m i n ( f u , ∑ d p v ) dp_umin(f_u,\sum dp_v) dpumin(fu,∑dpv)
CF613D Kingdom and its Cities 如果有一条边连接的都是重要城市输出-1 建完虚树比较暴力的跑就是 d p u , 0 / 1 dp_{u,0/1} dpu,0/1表示 u u u子树合法与 u u u连通的块中无/有一个特殊点所需的最小代价 对于 u u u为特殊点很显然只能转移到 d p u , 1 dp_{u,1} dpu,1和孩子节点全分开 d p u , 1 ∑ ( m i n ( d p v , 0 , d p v , 1 ) 1 ) dp_{u,1}\sum (min(dp_{v,0},dp_{v,1})1) dpu,1∑(min(dpv,0,dpv,1)1) 对于 u u u不为特殊点 d p u , 0 dp_{u,0} dpu,0转移同上 d p u , 1 dp_{u,1} dpu,1就是特意留下一个 d p v , 1 dp_{v,1} dpv,1转移过来且不断开这里转移就很不好搞了
我们发现一个贪心性质就是能留特殊点就尽量留下来所以我们就可以省一维然后多开一个数组 f u f_u fu来存储包含 u u u的连通块是否包含特殊点等到向父亲传递转移时迫不得已再断开
CF1111E Tree 先按照原树dfs序建虚树根节点不再是1选择特殊点中dfs序最小的那个一定要加入 r r r然后换虚树根跑dp dp状态部分很平常因为它是分了组的联想到第二类斯特林的递推式。 d p u , j ( j − b a d u ) ∗ d p u , j d p u , j − 1 dp_{u,j}(j-bad_u)*dp_{u,j}dp_{u,j-1} dpu,j(j−badu)∗dpu,jdpu,j−1 b a d u bad_u badu表示根节点到 u u u路径上特殊点个数 放入已有组或新开一个组单独放入遍历顺序我们只需保证在遍历到 u u u时 b a d u bad_u badu已经求出来了即可常规dfs就可以了
