2286: [Sdoi2011]消耗战

链接

分析

  虚树练习题。

  构建虚树,在虚树上DP。

  

  跟着gxb学虚-tree。。。

代码

 #include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cctype> using namespace std; const int N = ;
const int INF = 1e9; int head[N<<],nxt[N<<],to[N<<],w[N<<],TotE;
int deth[N],val[N],siz[N],dfn[N],fa[N],son[N],bel[N],sk[N<<],top,Time_index;
int A[N]; inline int read() {
int x = ,f = ;char ch =getchar();
for (; !isdigit(ch); ch=getchar()) if (ch=='-') f=-;
for (; isdigit(ch); ch=getchar()) x = x*+ch-'';
return x * f;
}
bool cmp(const int &a,const int &b) {
return dfn[a] < dfn[b];
}
void Add_edge(int u,int v,int c) {
++TotE;to[TotE] = v;w[TotE] = c;nxt[TotE] = head[u];head[u] = TotE;
++TotE;to[TotE] = u;w[TotE] = c;nxt[TotE] = head[v];head[v] = TotE;
}
void add_edge(int u,int v) {
++TotE;to[TotE] = v;nxt[TotE] = head[u];head[u] = TotE;
}
void dfs1(int u,int mn) {
val[u] = mn;
siz[u] = ;
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
if (v==fa[u]) continue;
fa[v] = u;
deth[v] = deth[u] + ;
dfs1(v,min(w[i],mn));
siz[u] += siz[v];
if (!son[u] || siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int top) {
bel[u] = top;
dfn[u] = ++Time_index;
if (!son[u]) return;
dfs2(son[u],top);
for (int i=head[u]; i; i=nxt[i]) {
int v = to[i];
if (v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
int Lca(int u,int v) {
while (bel[u] != bel[v]) {
if (deth[bel[u]] < deth[bel[v]]) swap(u,v);
u = fa[bel[u]];
}
if (deth[u] < deth[v]) return u;
return v;
}
void Insert(int p) {
int x = sk[top];
if (x==) {sk[++top] = p;return ;}
int lca = Lca(p,x);
if (lca == x) return; // 此题构建虚树不同的是,若x==lca,不加入p。
while (lca != x) {
int y = sk[--top];
if (dfn[y] < dfn[lca]) {
add_edge(lca,x);
sk[++top] = lca;
break;
}
add_edge(y,x);
x = sk[top];
}
sk[++top] = p;
}
long long DP(int u) {
if (!head[u]) return val[u];
long long ans = ;
for (int i=head[u]; i; i=nxt[i]) ans += DP(to[i]);
head[u] = ;
return min(ans,(long long)val[u]);
}
int main() {
int n = read();
for (int i=; i<n; ++i) {
int u = read(),v = read(),w = read();
Add_edge(u,v,w);
}
deth[] = ;
dfs1(,INF);
dfs2(,);
TotE = ;
memset(head,,sizeof(head)); int m = read();
while (m--) {
TotE = ;sk[top = ] = ; int k = read();
for (int i=; i<=k; ++i) A[i] = read();
sort(A+,A+k+,cmp);
for (int i=; i<=k; ++i) Insert(A[i]);
while (--top) add_edge(sk[top],sk[top+]); long long ans = ;
for (int i=head[]; i; i=nxt[i]) ans += DP(to[i]); // 单独处理1的情况,否则val[1]设为很大的longlong数,INF不够。
printf("%lld\n",ans);
head[] = ;
}
return ;
}

最新文章

  1. 生成彩条的MATLAB代码
  2. 解决css样式被内置样式覆盖的问题
  3. 谈谈 JavaScript 中的 this 指向问题
  4. js模拟Map对象,实现key---value
  5. QT GUI(主)线程与子线程之间的通信——使用跨线程的信号槽
  6. QLockFile,QRunInfo
  7. JavaScript两种方法来定义一个函数
  8. axis1,xfire,jUnit 测试案列+开Web Service开发指南+axis1.jar下载 代码
  9. 教你成为全栈工程师(Full Stack Developer) 〇-什么是全栈工程师
  10. 学生管理系统开发代码分析笔记:jsp+java bean+servlet技术
  11. Linux安装Tomcat-Nginx-FastDFS-Redis-Solr-集群——【第五集之补充-使用桥接模式实现虚拟机作为服务器,让同网段的其他主机远程连接】
  12. [Swift]LeetCode520. 检测大写字母 | Detect Capital
  13. 创建一个规范的django项目
  14. hadoop学习笔记-目录
  15. Codeforces 932E Team Work 数学
  16. linux环境下安装tomcat6
  17. Windows2012开机启动项设置
  18. iOS 源代码混淆(初步混淆)
  19. django2.0数据展示流程
  20. Flask 学习(一)概述及安装

热门文章

  1. MVC 默认路由 Areas
  2. Java 开发小常识
  3. Element-ui(el-table、el-pagination)实现表格分页
  4. HTML5开发必备工具
  5. 使用Excel调用ABAP系统的函数
  6. [转载]开启debug调试模式
  7. 简单的Nodejs模块
  8. nginx缓存批量清除
  9. PHP 5.4 on CentOS/RHEL 7.0, 6.5 and 5.10 via Yum
  10. MongoDB数据库CXX Driver编译