题目题解(12)讨论(5)排行较难 通过率38.07% 时间限制1秒 空间限制1024M知识点动态规划校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述对于给定的由 nn 个节点组成的无根树每一条边都可以被染上颜色初始时全部边均为白色。现在选中树上 kk 个不同的点并将它们标记随后定义如果一条树边 (u,v)(u,v) 满足节点 uu 和 vv 同时被标记那么这条树边自动被染为红色不需要花费任何代价。现在你可以额外选择一些树边将它们染成红色每染一条边需要花费 11 点代价。请你计算最小的染色代价使得任意一个被标记的点都可以通过被染成红色的边到达至少一个未被标记的点。并输出不同的染色方案数量。输入描述第一行输入两个整数 n,k(2≦n≦105; 1≦kn)n,k(2≦n≦105; 1≦kn) 代表树的节点数、被标记的点数。第二行输入 kk 个不同的整数 a1,a2,…,ak(1≦ai≦n)a1,a2,…,ak(1≦ai≦n) 代表被标记的点的编号。此后 n−1n−1 行第 ii 行输入两个整数 ui,vi(1≦ui,vi≦n,ui≠vi)ui,vi(1≦ui,vi≦n,uivi) 代表第 ii 条树边连接 uiui 和 vivi。输出描述在一行上输出两个整数代表最小的染色代价、满足条件的染色方案数量。由于染色方案数量可能很大请输出对 10971097 取模后的结果。示例1输入11 6 8 2 4 7 9 6 8 10 8 9 1 8 1 11 1 3 11 2 5 6 2 5 4 2 7 6复制输出3 4复制说明在这个样例中树的形态如下图所示。TOPACM 模式是否格式化代码1234567891011121314时间限制C/C 1秒其他语言#include iostream #include vector using namespace std; typedef long long LL; const int MOD 1e9 7; const int maxn 200005; bool vis[maxn] {false}; bool masked[maxn] {false}; vectorint G[maxn]; // 邻接表 // 统计v能到达的neighbor数量 void DFS(int v, int cnt){ if(vis[v]) return; vis[v] true; for(int i0; iG[v].size(); i){ if(masked[G[v][i]] vis[G[v][i]] false){ // 若是标记节点继续深入搜索 DFS(G[v][i], cnt); }else if(vis[G[v][i]] false){ // 若是没有访问的邻居节点 cnt; } } } int main() { int n, k, u, v; cin n k; for(int i0; ik; i){ cin v; masked[v] true; } for(int i0; in-1; i){ cin u v; G[u].push_back(v); G[v].push_back(u); } LL ans 1, cost 0; for(int i1; in; i){ if(masked[i] vis[i] false){ int cnt 0; DFS(i, cnt); cost; // 最小代价为标记节点连通块数量 ans (ans * cnt) % MOD; // 方案数为当前方案数乘上每个连通块的邻居节点数量 } } cout cost ans; return 0; } // 64 位输出请用 printf(%lld)
HJ138 在树上游玩
题目题解(12)讨论(5)排行较难 通过率38.07% 时间限制1秒 空间限制1024M知识点动态规划校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述对于给定的由 nn 个节点组成的无根树每一条边都可以被染上颜色初始时全部边均为白色。现在选中树上 kk 个不同的点并将它们标记随后定义如果一条树边 (u,v)(u,v) 满足节点 uu 和 vv 同时被标记那么这条树边自动被染为红色不需要花费任何代价。现在你可以额外选择一些树边将它们染成红色每染一条边需要花费 11 点代价。请你计算最小的染色代价使得任意一个被标记的点都可以通过被染成红色的边到达至少一个未被标记的点。并输出不同的染色方案数量。输入描述第一行输入两个整数 n,k(2≦n≦105; 1≦kn)n,k(2≦n≦105; 1≦kn) 代表树的节点数、被标记的点数。第二行输入 kk 个不同的整数 a1,a2,…,ak(1≦ai≦n)a1,a2,…,ak(1≦ai≦n) 代表被标记的点的编号。此后 n−1n−1 行第 ii 行输入两个整数 ui,vi(1≦ui,vi≦n,ui≠vi)ui,vi(1≦ui,vi≦n,uivi) 代表第 ii 条树边连接 uiui 和 vivi。输出描述在一行上输出两个整数代表最小的染色代价、满足条件的染色方案数量。由于染色方案数量可能很大请输出对 10971097 取模后的结果。示例1输入11 6 8 2 4 7 9 6 8 10 8 9 1 8 1 11 1 3 11 2 5 6 2 5 4 2 7 6复制输出3 4复制说明在这个样例中树的形态如下图所示。TOPACM 模式是否格式化代码1234567891011121314时间限制C/C 1秒其他语言#include iostream #include vector using namespace std; typedef long long LL; const int MOD 1e9 7; const int maxn 200005; bool vis[maxn] {false}; bool masked[maxn] {false}; vectorint G[maxn]; // 邻接表 // 统计v能到达的neighbor数量 void DFS(int v, int cnt){ if(vis[v]) return; vis[v] true; for(int i0; iG[v].size(); i){ if(masked[G[v][i]] vis[G[v][i]] false){ // 若是标记节点继续深入搜索 DFS(G[v][i], cnt); }else if(vis[G[v][i]] false){ // 若是没有访问的邻居节点 cnt; } } } int main() { int n, k, u, v; cin n k; for(int i0; ik; i){ cin v; masked[v] true; } for(int i0; in-1; i){ cin u v; G[u].push_back(v); G[v].push_back(u); } LL ans 1, cost 0; for(int i1; in; i){ if(masked[i] vis[i] false){ int cnt 0; DFS(i, cnt); cost; // 最小代价为标记节点连通块数量 ans (ans * cnt) % MOD; // 方案数为当前方案数乘上每个连通块的邻居节点数量 } } cout cost ans; return 0; } // 64 位输出请用 printf(%lld)
