[虚树模板] 洛谷P2495 消耗战
2024-08-30 18:27:47
[update]
好像有个东西叫笛卡尔树，好像是这样建的.....
inline void build_d() {
stk[top = ] = ;
for(int i = ; i <= n; i++) {
while(top && val[stk[top]] <= val[i]) {
ls[i] = stk[top];
top--;
}
if(ls[i]) {
fa[ls[i]] = i;
}
if(top) {
fa[i] = stk[top];
rs[stk[top]] = i;
}
stk[++top] = i;
}
RT = stk[];
return;
}
题意：给定树上k个点，求切断这些点到根路径的最小代价。∑k <= 5e5
解：虚树。
构建虚树大概是这样的：设加入点与栈顶的lca为y，比较y和栈中第二个元素的DFS序大小关系。
代码如下：
inline bool cmp(const int &a, const int &b) {
return pos[a] < pos[b];
}
inline void build_t() {
std::sort(imp + , imp + k + , cmp);
TP = top = ;
stk[++top] = imp[];
use[imp[]] = Time;
E[imp[]] = ;
for(int i = ; i <= k; i++) {
int x = imp[i], y = lca(x, stk[top]);
if(use[x] != Time) {
use[x] = Time;
E[x] = ;
}
if(use[y] != Time) {
use[y] = Time;
E[y] = ;
}
while(top > && pos[y] <= pos[stk[top - ]]) {
ADD(stk[top - ], stk[top]);
top--;
}
if(stk[top] != y) {
ADD(y, stk[top]);
stk[top] = y;
}
stk[++top] = x;
}
while(top > ) {
ADD(stk[top - ], stk[top]);
top--;
}
RT = stk[top];
return;
}
然后本题建虚树跑DP就行了。注意虚树根节点的DP初值和虚树的边权。
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = ;
const LL INF = 1e18; struct Edge {
int nex, v;
LL len;
}edge[N << ], EDGE[N << ]; int tp, TP; int e[N], siz[N], stk[N], top, Time, n, fa[N][], k, RT, num, pos[N], pw[N], now[N], imp[N], E[N], d[N], use[N];
LL f[N], small[N][]; inline void ADD(int x, int y, LL z) {
TP++;
EDGE[TP].v = y;
EDGE[TP].len = z;
EDGE[TP].nex = E[x];
E[x] = TP;
return;
} inline void add(int x, int y, LL z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} void DFS_1(int x, int father) { // get fa small
fa[x][] = father;
d[x] = d[father] + ;
pos[x] = ++num;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == father) {
continue;
}
small[y][] = edge[i].len;
DFS_1(y, x);
}
return;
} inline int lca(int x, int y) {
if(d[x] > d[y]) {
std::swap(x, y);
}
int t = pw[n];
while(t >= && d[x] < d[y]) {
if(d[fa[y][t]] >= d[x]) {
y = fa[y][t];
}
t--;
}
if(x == y) {
return x;
}
t = pw[n];
while(t >= && fa[x][] != fa[y][]) {
if(fa[x][t] != fa[y][t]) {
x = fa[x][t];
y = fa[y][t];
}
t--;
}
return fa[x][];
} inline bool cmp(const int &a, const int &b) {
return pos[a] < pos[b];
} inline LL getMin(int x, int y) {
LL ans = INF;
int t = pw[d[y] - d[x]];
while(t >= && y != x) {
if(d[fa[y][t]] >= d[x]) {
ans = std::min(ans, small[y][t]);
y = fa[y][t];
}
t--;
}
return ans;
} inline void build_t() {
std::sort(imp + , imp + k + , cmp);
TP = top = ;
stk[++top] = imp[];
use[imp[]] = Time;
E[imp[]] = ;
for(int i = ; i <= k; i++) {
int x = imp[i], y = lca(x, stk[top]);
if(use[x] != Time) {
use[x] = Time;
E[x] = ;
}
if(use[y] != Time) {
use[y] = Time;
E[y] = ;
}
while(top > && pos[y] <= pos[stk[top - ]]) {
ADD(stk[top - ], stk[top], getMin(stk[top - ], stk[top]));
top--;
}
if(stk[top] != y) {
ADD(y, stk[top], getMin(y, stk[top]));
stk[top] = y;
}
stk[++top] = x;
}
while(top > ) {
ADD(stk[top - ], stk[top], getMin(stk[top - ], stk[top]));
top--;
}
RT = stk[top];
return;
} void DFS(int x) {
siz[x] = (now[x] == Time);
LL temp = ;
for(int i = E[x]; i; i = EDGE[i].nex) {
int y = EDGE[i].v;
f[y] = EDGE[i].len;
DFS(y);
siz[x] += siz[y];
if(siz[y]) {
temp += f[y];
}
}
if(now[x] != Time) {
f[x] = std::min(f[x], temp);
}
return;
} void out(int x) {
return;
} int main() {
scanf("%d", &n);
/*if(n > 100) {
return -1;
}*/
int x, y; LL z;
for(int i = ; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
// get lca min_edge
DFS_1(, );
for(int i = ; i <= n; i++) {
pw[i] = pw[i >> ] + ;
}
for(int j = ; j <= pw[n]; j++) {
for(int i = ; i <= n; i++) {
fa[i][j] = fa[fa[i][j - ]][j - ];
small[i][j] = std::min(small[i][j - ], small[fa[i][j - ]][j - ]);
}
} int m;
scanf("%d", &m);
for(Time = ; Time <= m; Time++) {
scanf("%d", &k);
//printf("\n k = %d \n", k);
for(int i = ; i <= k; i++) {
scanf("%d", &imp[i]);
now[imp[i]] = Time;
}
//printf("input over \n");
build_t();
//out(RT);
f[RT] = getMin(, RT);
DFS(RT);
printf("%lld\n", f[RT]);
} return ;
}
AC代码
最新文章
- 【.net深呼吸】WPF异步加载大批量图像
- GIT/node使用
- java9-3 返回类型
- 关于struts 2中的日期问题
- phalcon几种分页方法
- mahout的安装、配置及运行java程序
- B - Dining - poj 3281（最大流）
- SEO,你敢说你会吗?
- Eclipse 乱码问题 修改设置
- L5,no wrong numbers
- 201521123066 《Java程序设计》第十二周实验总结
- 关于SSDT
- SQL SERVER 2008远程数据库移植到本地的方法
- redis安装(单节点）
- EVE-NG简单入门介绍
- 最近的AI
- Python 的 14 张思维导图汇总
- tf.argmax
- eclipse 使用总结
- Asp.Net通过ODBC连接Oracle数据库