合肥专业做网站的公司哪家好,网站后台管理模板html,WordPress 前台 注册用户 插件,做网站需要虚拟主机还是服务器虚树(Virtual Tree)学习笔记 一道题目(BZOJ-2286消耗战) Description 在一场战争中#xff0c;战场由n个岛屿和n-1个桥梁组成#xff0c;保证每两个岛屿间有且仅有一条路径可达。现在#xff0c;我军已经侦查到敌军的总部在编号为1的岛屿#xff0c;而且他们已经没有足够多… 虚树(Virtual Tree)学习笔记 一道题目(BZOJ-2286消耗战) Description 在一场战争中战场由n个岛屿和n-1个桥梁组成保证每两个岛屿间有且仅有一条路径可达。现在我军已经侦查到敌军的总部在编号为1的岛屿而且他们已经没有足够多的能源维系战斗我军胜利在望。已知在其他k个岛屿上有丰富能源为了防止敌军获取能源我军的任务是炸毁一些桥梁使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同所以炸毁不同的桥梁有不同的代价我军希望在满足目标的同时使得总代价最小。 侦查部门还发现敌军有一台神秘机器。即使我军切断所有能源之后他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁而且会重新随机资源分布但可以保证的是资源不会分布到1号岛屿上。不过侦查部门还发现了这台机器只能够使用m次所以我们只需要把每次任务完成即可。 Input 第一行一个整数n代表岛屿数量。 接下来n-1行每行三个整数u,v,w代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连保证1u,vn且1c100000。 第n1行一个整数m代表敌方机器能使用的次数。 接下来m行每行一个整数ki代表第i次后有ki个岛屿资源丰富接下来k个整数h1,h2,…hk表示资源丰富岛屿的编号。 Output 输出有m行分别代表每次任务的最小代价。 树的点数少 如果树的点数少可以用\(dp[u]\)表示子树的所有关键点都不连通的最小代价如果子节点\(v\)是关键点则一定断开\(uv\)这条边否则选择是断开\(uv\)还是使用子树内的边来阻断转移即可\(O(nq)\)。 虚树 Virtual Tree 不难发现其中很多点是无用的对我们有用的点其实只有所有的关键点和他们之间的\(lca\)虚树就是在不改变祖先与后代关系的情况下保留了一些有用点把一整颗树的信息进行压缩建出一棵小树。我们可以通过将关键点按\(dfs\)序排序求出一些相邻点的\(lca\)将他们加入虚树中同时保持祖先与后代的关系这里可以看出询问\(n\)个关键点时虚树的节点数N小于等于\(2n-1\)使用单调栈建虚树为了方便我们把\(1\)加入虚树中。用单调栈来维护一条虚树上的链也就是一个栈里相邻的两个节点在虚树上也是相邻的而且栈是从底部到栈首单调\(dfs\)序递增的。太懒了。。算法细节还是看这里对于本题建出虚树后我们还要维护一些被压缩路径的最小值可以倍增维护#include bits/stdc.h
typedef long long ll;
const int N 250010;
using namespace std;
int n, q;
struct edge { int e, w, nxt; } E[N 1];
int cc, h[N];
void add(int u,int v,int w) {E[cc].e v; E[cc].w w; E[cc].nxt h[u]; h[u] cc; cc;
}
int dfn[N], id, fa[N][20], dep[N], mn[N][20];
void dfs(int u, int pre) {dfn[u] id; fa[u][0] pre; dep[u] dep[pre] 1;for(int i 1; i 19; i) {fa[u][i] fa[fa[u][i-1]][i-1];mn[u][i] min(mn[u][i-1], mn[fa[u][i-1]][i-1]);}for(int i h[u]; ~i; i E[i].nxt) {int v E[i].e, w E[i].w;if(v pre) continue;mn[v][0] w; dfs(v, u);}
}
int lca(int u, int v) {if(dep[u] dep[v]) swap(u, v);for(int i 19; i 0; --i) if(dep[fa[v][i]] dep[u]) v fa[v][i];if(u v) return v;for(int i 19; i 0; --i) if(fa[u][i] ! fa[v][i]) u fa[u][i], v fa[v][i];return fa[u][0];
}
int calmn(int u, int v) {int ans INT_MAX;if(dep[u] dep[v]) swap(u, v);for(int i 19; i 0; --i) if(dep[fa[v][i]] dep[u]) ans min(ans, mn[v][i]), v fa[v][i];return ans;
}
bool cmp(int u, int v) { return dfn[u] dfn[v]; }
int a[N], mk[N], stc[N], top;
void build(int a[], int m) {sort(a1, a1m, cmp); stc[top 1] 1; cc 0; h[1] -1;for(int p, i 1; i m; i) {if(a[i] ! 1) {p lca(stc[top], a[i]);if(p ! stc[top]) {while(dfn[p] dfn[stc[top-1]]) {int w calmn(stc[top-1],stc[top]);add(stc[top-1],stc[top],w); -- top;}if(dfn[p] dfn[stc[top-1]]) {int w calmn(p,stc[top]); h[p] -1;add(p, stc[top], w), stc[top] p;}else {int w calmn(p,stc[top]);add(p, stc[top--], w);}}h[a[i]] -1, stc[top] a[i];}}for(int w, i 1; i top; i) {w calmn(stc[i], stc[i1]);add(stc[i],stc[i1],w);}
}
ll dp[N];
void Dp(int u) {dp[u] 0;for(int i h[u]; ~i; i E[i].nxt) {Dp(E[i].e);if(mk[E[i].e]) dp[u] E[i].w;else dp[u] min(1ll*E[i].w, dp[E[i].e]);}
}
int main() {scanf(%d,n); memset(h,-1,sizeof(h));for(int u, v, w, i 1; i n; i) {scanf(%d%d%d,u,v,w);add(u,v,w), add(v,u,w);} dfs(1,0);scanf(%d,q);while(q--) { int m;scanf(%d,m);for(int i 1; i m; i) scanf(%d,a[i]), mk[a[i]] 1;build(a, m); Dp(1);printf(%lld\n, dp[1]);for(int i 1; i m; i) mk[a[i]] 0;}
} 转载于:https://www.cnblogs.com/RRRR-wys/p/10310371.html
