HJ135 计树

知识点动态规划校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定由 nn 个结点构成、以 11 号节点为根节点的有根树选中其中 kk 个节点记为集合 VV。现在你需要构建一个计数数组 cntcnt其中 cnticnti​ 表示节点 ii 作为 LCA 的次数。具体操作如下∙ ∙从集合 VV 中选择一个节点 uu∙ ∙从集合 VV 中选择一个节点 vv可能会与 uu 相同∙ ∙记 u,vu,v 两个节点的最近公共祖先LCA为 ii更新 cnticnti​ 为 cnti1cnti​1。对于全部 k2k2 个选取方式重复上述操作。最后输出 cntcnt 数组。输入描述第一行输入一个整数 n(1≦n≦105)n(1≦n≦105) 代表树的节点数。此后 n−1n−1 行第 ii 行输入两个整数 ui,vi(1≦ui,vi≦n; ui≠vi)ui​,vi​(1≦ui​,vi​≦n; ui​​vi​) 代表树上第 ii 条边连接节点 uiui​ 和 vivi​。第 n1n1 行输入一个整数 k(1≦k≦n)k(1≦k≦n) 代表集合 VV 的大小。第 n2n2 行输入 kk 个整数 a1,a2,…,ak(1≦ai≦n)a1​,a2​,…,ak​(1≦ai​≦n) 代表集合 VV 中的节点。输出描述在一行上输出 nn 个整数其中第 ii 个整数表示节点 ii 作为 LCA 的次数即 cnticnti​ 的值。示例1输入5 1 2 1 3 2 4 2 5 3 2 3 4复制输出4 3 1 1 0复制说明在这个样例中树的形态如下图所示。#include iostream #include vector using namespace std; const int MAXN 100005; vectorvectorint adj; // 邻接表 bool isInV[MAXN] {false}; // 统计节点是否属于集合V long long countV[MAXN] {0}; // countV[u]统计以u为根的子树中含有V节点的数量 long long LcaCount[MAXN] {0}; // Final answer cnt[u] // DFS function to calculate countV and LcaCount long long dfs(int u, int p) { // long long current_v_num isInV[u] true ? 1 : 0; long long child_v_size 0; for(auto v: adj[u]){ if(v ! p){ // 只往孩子节点方向遍历防止往回遍历到父节点 long long child_v_num dfs(v, u); current_v_num child_v_num; child_v_size child_v_num*child_v_num; } } LcaCount[u] current_v_num * current_v_num - child_v_size; // 记录LCA值 countV[u] current_v_num; return current_v_num; } int main() { ios_base::sync_with_stdio(false); // Faster I/O cin.tie(NULL); int n, u, v, k; cin n; adj.resize(n 1); for(int i0; in-1; i){ cin u v; adj[u].push_back(v); adj[v].push_back(u); } cin k; for(int i0; ik; i){ cin u; isInV[u] true; } dfs(1, 0); // 从根节点开始遍历根节点的父节点设为0 for(int i1; in; i){ cout LcaCount[i] (in ? : ); } }