西安电子科技大学信息化建设处网站,做网站得多钱,邯郸市中小学健康管理平台登录,wdcp wordpress搬家虚树是什么
虚树指在原树上选择需要的点和它们的LCALCALCA组成的一棵树。这样可以使在树DP时顶点数更少#xff0c;从而减少时间复杂度。一般用于有多组数据且能保证所有数据访问的点的和不超过规定范围。 情景代入#xff1a;SDOI2011消耗战
SDOI2011消耗战
题目大意
给…虚树是什么
虚树指在原树上选择需要的点和它们的LCALCALCA组成的一棵树。这样可以使在树DP时顶点数更少从而减少时间复杂度。一般用于有多组数据且能保证所有数据访问的点的和不超过规定范围。 情景代入SDOI2011消耗战
SDOI2011消耗战
题目大意
给出一棵树根节点为一号点有nnn顶点n−1n-1n−1条边每条边都有边权断掉一条边的代价为这条边的边权。有mmm次询问每次询问给出kkk个询问点问使这kkk个点都不和根节点相连的最小代价。
数据范围
1≤n≤2.5×105,1≤m≤5×105,1≤∑k≤5×1051\leq n\leq 2.5\times 10^5,1\leq m\leq 5\times 10^5,1\leq \sum k\leq 5\times 10^51≤n≤2.5×105,1≤m≤5×105,1≤∑k≤5×105 做法
我们可以用树型DP。设f[i]f[i]f[i]表示子树iii与根节点断开的代价md[i]md[i]md[i]表示点iii到根节点的最小边权。分类讨论一下
如果点iii是询问点那么f[i]md[i]f[i]md[i]f[i]md[i]如果点iii不是询问点那么f[i]min(md[i],∑j∈sonifj)f[i]min(md[i],\sum\limits_{j\in son_i}f_j)f[i]min(md[i],j∈soni∑fj)
可以用dfs来解决。
但如果直接这样做的话时间复杂度为O(nm)O(nm)O(nm)显然会TLE。又因为kkk的和在5×1055\times 10^55×105以内所以我们可以用虚树来解决。
对于每次询问我们将询问点和它们的LCALCALCA放到虚树中。举几个例子
对于如下一棵树 如果查询点为6,10那么构成的虚树如下 放进虚树的点即为查询点和它们的LCALCALCA。
因为每加入一个点最多只会产生一个LCALCALCA所以如果有kkk个有效的点则虚树上最多只会有2k2k2k个点。 虚树如何建立
那么虚树该如何建立呢
首先我们对原树进行dfs按dfs序给每一个点打上时间戳dfn。
将所有要查询的点按dfn排序用栈来维护根节点到当前点的链。
一开始根节点入栈st[top]1st[top]1st[top]1
设当前加入的点为xxx
用whilewhilewhile循环如果dfn[s[top−1]]≥dfn[lca(s[top],x)]dfn[s[top-1]]\geq dfn[lca(s[top],x)]dfn[s[top−1]]≥dfn[lca(s[top],x)]那么lcalcalca为点st[top]st[top]st[top]的祖先连边(st[top−1],st[top]),top−−(st[top-1],st[top]),top--(st[top−1],st[top]),top−−ififif判断如果dfn[lca(st[top],x)]≠dfn[st[top]]dfn[lca(st[top],x)]\neq dfn[st[top]]dfn[lca(st[top],x)]dfn[st[top]]则lcalcalca在点st[top]st[top]st[top]和st[top−1]st[top-1]st[top−1]之间连边(lca,st[top]),st[top]lca(lca,st[top]),st[top]lca(lca,st[top]),st[top]lca将xxx入栈然后退出
当所有点都考虑完了之后还要对栈中的点依次连边并退栈。
code
void insert(int x){if(top1){s[top]x;return;}int lcaLCA(x,s[top]);
// if(lcas[top]) return;while(top1dfn[s[top-1]]dfn[lca]){add(s[top-1],s[top]);--top;}if(lca!s[top]){add(lca,s[top]);s[top]lca;}s[top]x;
}其中被注释的一行是一般虚树加点操作没有的但这道题需要。因为这道题如果一个点一定不与根节点相连则其子树叶一定满足条件所以子树可以不用考虑。而在最底部的s[top]s[top]s[top]一定不是LCALCALCA所以遇到这种情况直接return即可。
加点过程如下
code
dfs(1,0);
while(m--){scanf(%d,k);for(int i1;ik;i){scanf(%d,a[i]);}sort(a1,ak1,cmp);s[top1]1;for(int i1;ik;i){insert(a[i]);}while(top1){v[s[top-1]].push_back(s[top]);--top;}printf(%lld\n,dp(1));
}SDOI2011消耗战
用虚树来做的话时间复杂度为O(∑klogk)O(\sum k\log k)O(∑klogk)。
code
#includebits/stdc.h
using namespace std;
const int N250000;
int n,m,k,tot0,dt0,top,d[500005],l[500005],r[500005];
int a[N5],s[N5],fa[N5],tp[N5],dep[N5],siz[N5],son[N5],dfn[N5];
long long w[500005],md[N5];
vectorintv[N5];
bool cmp(int ax,int bx){return dfn[ax]dfn[bx];
}
void add(int xx,int yy,long long zz){l[tot]r[xx];d[tot]yy;r[xx]tot;w[tot]zz;
}
void dfs1(int u,int f){dep[u]dep[f]1;fa[u]f;siz[u]1;for(int ir[u];i;il[i]){if(d[i]f) continue;md[d[i]]min(w[i],md[u]);dfs1(d[i],u);siz[u]siz[d[i]];if(siz[d[i]]siz[son[u]]) son[u]d[i];}
}
void dfs2(int u,int f){dfn[u]dt;if(son[u]){tp[son[u]]tp[u];dfs2(son[u],u);}for(int ir[u];i;il[i]){if(d[i]f||d[i]son[u]) continue;tp[d[i]]d[i];dfs2(d[i],u);}
}
int gt(int x,int y){while(tp[x]!tp[y]){if(dep[tp[x]]dep[tp[y]]) swap(x,y);xfa[tp[x]];}if(dep[x]dep[y]) swap(x,y);return x;
}
void insert(int x){if(top1){s[top]x;return;}int lcagt(x,s[top]);if(lcas[top]) return;while(top1dfn[s[top-1]]dfn[lca]){v[s[top-1]].push_back(s[top]);--top;}if(s[top]!lca){v[lca].push_back(s[top]);s[top]lca;}s[top]x;
}
long long dp(int u){if(v[u].size()0) return md[u];long long sum0;for(int i0;iv[u].size();i){sumdp(v[u][i]);}v[u].clear();return min(sum,md[u]);
}
int main()
{int x,y;long long z;scanf(%d,n);md[1]1e18;for(int i1;in;i){scanf(%d%d%lld,x,y,z);add(x,y,z);add(y,x,z);}dfs1(1,0);tp[1]1;dfs2(1,0);scanf(%d,m);while(m--){scanf(%d,k);for(int i1;ik;i){scanf(%d,a[i]);}sort(a1,ak1,cmp);s[top1]1;for(int i1;ik;i){insert(a[i]);}while(top1){v[s[top-1]].push_back(s[top]);--top;}printf(%lld\n,dp(1));}return 0;
}
