【ybt金牌导航5-3-2】【luogu P2495】消耗战
导航 Luogu ybt 金牌
2023-09-27 14:28:28 时间
消耗战
题目链接:ybt金牌导航5-3-2 / luogu P2495
题目大意
有一个树,每个边有切断的费用,每次选一些点(不会选 1 点),问你最少要用多少费用切边,使得所有选点的点都不能与 1 点连通。
思路
首先容易想到如果一次询问的话,它就是一个树形 DP。
大概就是记录每个点被割最少要多少费用(就是
1
1
1 点到它之间的边之间边权最小的那个),然后从叶节点从下而上 DP,可以割自己,也可以把子树的都处理掉。
但是如果自己一定要割就没有第二种,因为你割了自己又割儿子肯定不优。
但是它是多组询问,那你就建个虚树搞搞就好了。
(询问虚树上的距离不要用 LCA 来搞,我一开始是这么搞的,然后卡了三页评测的常也只有
90
90
90)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
struct node {
ll x;
int to, nxt;
}e[500001], e_[250001];
struct kong {
int fa;
}t[250001];
int n, x, y, z, le[250001], KK, lca, tmpp;
int fa[250001][18], dfn[250001], m, nn;
int sta[250001], deg[250001];
int le_[250001], KK_, sp[250001];
ll f[250001], minv[250001], re;
bool real[500001];
inline int read() {
re = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re;
}
inline void write(ll x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline ll Min(ll x, ll y) {
return (x < y) ? (x) : (y);
}
inline void add(int x, int y, ll z) {
e[++KK] = (node){z, y, le[x]}; le[x] = KK;
e[++KK] = (node){z, x, le[y]}; le[y] = KK;
}
inline void add_(int x, int y) {
e_[++KK_] = (node){0, y, le_[x]}; le_[x] = KK_;
}
void dfs(int now, int father) {
deg[now] = deg[father] + 1;
fa[now][0] = father;
dfn[now] = ++tmpp;
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to ^ father) {
minv[e[i].to] = Min(minv[now], e[i].x);//求出割这个点最少要的费用(选 1 点到它费用最小的边)
dfs(e[i].to, now);
}
}
inline bool cmp(int x, int y) {//按 dfs 序排序
return dfn[x] < dfn[y];
}
inline int LCA(int x, int y) {//求LCA
if (deg[x] < deg[y]) swap(x, y);
for (int i = 15; i >= 0; i--)
if (deg[fa[x][i]] >= deg[y])
x = fa[x][i];
if (x == y) return x;
for (int i = 15; i >= 0; i--)
if (fa[x][i] ^ fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
void build_kong() {//建虚树
tmpp = 0;
sort(sp + 1, sp + sp[0] + 1, cmp);
// nn = unique(sp + 1, sp + sp[0] + 1) - sp - 1;
nn = sp[0];
sta[0] = 1;
for (int i = 1; i <= nn; i++) {
if (!tmpp) {
sta[++tmpp] = sp[i];
t[sp[i]].fa = 0;
}
else {
lca = LCA(sp[i], sta[tmpp]);
while (deg[lca] < deg[sta[tmpp]]) {
if (deg[lca] > deg[sta[tmpp - 1]]) {
t[sta[tmpp]].fa = lca;
}
tmpp--;
}
while (lca ^ sta[tmpp]) {
sp[++sp[0]] = lca;
t[lca].fa = sta[tmpp];
sta[++tmpp] = lca;
}
t[sp[i]].fa = lca;
sta[++tmpp] = sp[i];
}
}
// sort(sp + 1, sp + sp[0] + 1, cmp);
for (int i = 1; i <= sp[0]; i++)
if (sp[i] ^ 1)
add_((t[sp[i]].fa) ? (t[sp[i]].fa) : 1, sp[i]);
}
void dfs_(int now, int father) {//树状 DP
f[now] = minv[now];//这这里(那下面的都可以不割)
ll tmp = 0;
for (int i = le_[now]; i; i = e_[i].nxt)
if (e_[i].to ^ father) {
dfs_(e_[i].to, now);
tmp += f[e_[i].to];//选把下面割个的都割掉,不割这里
}
if (!real[now]) f[now] = Min(f[now], tmp);//如果这个这个点要割,那不能只割下面的,一定要选上面的割
le_[now] = 0;
real[now] = 0;
}
int main() {
// freopen("read.txt", "r", stdin);
// freopen("write.txt", "w", stdout);
n = read();
for (int i = 1; i < n; i++) {
x = read(); y = read(); z = read();
add(x, y, z);
}
tmpp = 0;
minv[1] = 1e18;
dfs(1, 0);
for (int i = 1; i <= 15; i++)//倍增预处理LCA
for (int j = 1; j <= n; j++)
fa[j][i] = fa[fa[j][i - 1]][i - 1];
m = read();
while (m--) {
sp[0] = read();
for (int i = 1; i <= sp[0]; i++) {
sp[i] = read();
real[sp[i]] = 1;//标记哪些点是一定要隔开的
}
sp[++sp[0]] = 1;
build_kong();//建虚树
dfs_(1, 0);
write(f[1]);
putchar('\n');
KK_ = 0;
}
return 0;
}
相关文章
- 【ybt金牌导航4-6-4】【luogu P3402】可持久化并查集
- 【ybt金牌导航8-3-1】【luogu P4781】函数求值 / 【模板】拉格朗日插值
- 【ybt金牌导航6-3-1】【luogu P4168】区间众数 / 蒲公英 / 分块例题
- 【ybt金牌导航5-3-1】【luogu P3233】世界树 / 虚树例题
- 【ybt金牌导航6-3-3】【luogu P4135】偶数个数 / 作诗(分块)
- 【ybt金牌导航8-2-5】【luogu P3265】【bzoj 4004】装备购买(贪心)(实数线性基)(高斯消元)
- 【ybt金牌导航8-5-4】【luogu P4128】有色图(dfs)(Polya定理)(分类讨论)
- 【ybt金牌导航1-1-8】【luogu P3750】关灯游戏 / 分手是祝愿
- 【ybt金牌导航2-3-3】【luogu P3975】K小子串 / 弦论
- 【ybt金牌导航2-1-3】【luogu P4555】最长双回文串(两种方法)
- 【ybt金牌导航1-5-1】【ybt金牌导航1-5-2】【luogu P2365】任务安排1 / 任务安排2 / 任务安排
- 【ybt金牌导航6-5-4】【luogu P3157】动态逆序对(CDQ分治)(树状数组)
- 【ybt金牌导航6-2-1】【luogu P3201】梦幻布丁 / 启发式合并例题
- 【ybt金牌导航3-6-6】【luogu P4171】满汉全席
- 【ybt金牌导航3-6-2】【luogu UVA11294】【POJ 3648】婚礼 / Wedding
- 【ybt金牌导航3-5-5】【luogu P1262】间谍网络
- 【ybt金牌导航5-4-2】【luogu P3203】弹飞绵羊
- 【ybt金牌导航4-2-4】【luogu P4148】简单题
- 【ybt金牌导航4-2-3】【luogu P4357】K远点对
- 【ybt金牌导航4-2-1】【luogu P4169】[Violet]天使玩偶 / SJY摆棋子(K-D tree 模板)
- 【ybt金牌导航4-1-2】【luogu P2713】合并游戏 / 罗马游戏
- 【ybt金牌导航5-1-2】【luogu P2146】软件管理 / 软件包管理器
- 【ybt金牌导航4-3-5】【luogu P3369】普通平衡树(Splay 做法)