在树上游玩【牛客tracker 每日一题】

在树上游玩时间限制1秒 空间限制1024M知识点动态规划网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的由n nn个节点组成的无根树每一条边都可以被染上颜色初始时全部边均为白色。现在选中树上k kk个不同的点并将它们标记随后定义如果一条树边( u , v ) (u,v)(u,v)满足节点u uu和v vv同时被标记那么这条树边自动被染为红色不需要花费任何代价。现在你可以额外选择一些树边将它们染成红色每染一条边需要花费1 11点代价。请你计算最小的染色代价使得任意一个被标记的点都可以通过被染成红色的边到达至少一个未被标记的点。并输出不同的染色方案数量。输入描述第一行输入两个整数n , k ( 2 ≦ n ≦ 10 5 ; 1 ≦ k n ) n,k(2≦n≦10^5; 1≦kn)n,k(2≦n≦105;1≦kn)代表树的节点数、被标记的点数。第二行输入k kk个不同的整数a 1 , a 2 , … , a k ( 1 ≦ a i ≦ n ) a_1,a_2,…,a_k(1≦a_i≦n)a1​,a2​,…,ak​(1≦ai​≦n)代表被标记的点的编号。此后n − 1 n−1n−1行第i ii行输入两个整数u i , v i ( 1 ≦ u i , v i ≦ n , u i ≠ v i ) u_i,v_i(1≦u_i,v_i≦n,u_i≠v_i)ui​,vi​(1≦ui​,vi​≦n,ui​vi​)代表第i ii条树边连接u i u_iui​和v i v_ivi​​。输出描述在一行上输出两个整数代表最小的染色代价、满足条件的染色方案数量。由于染色方案数量可能很大请输出对10 9 7 10^971097取模后的结果。示例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说明在这个样例中树的形态如下图所示。解题思路本题是树的连通分量划分 乘法原理计数的经典题型核心是将问题转化为标记点连通块的出口边统计通过DFS遍历求解连通块并计数可选边最终得到最小代价与方案总数。1. 问题等价转化免费红边规则两端均为标记点的边会自动染成红色无需花费。这些边将所有标记点分割为若干个互不连通的「标记连通块」块内部的所有标记点已经通过免费红边互相可达。目标要求拆解每个标记点必须能通过红边到达至少一个未标记点等价于每个标记连通块至少额外染红一条通往未标记区域的边出口边让整个块连接到未标记的部分。最小代价结论最小染色代价 标记连通块的总个数每个块恰好染一条出口边即可达到最优。方案数结论每个连通块对应若干条可选的出口边一端在块内标记点、另一端为未标记点的边总方案数为所有连通块的可选边数相乘结果对10 9 7 10^971097取模。2. 算法实现DFS遍历连通块建图与标记用邻接表存储整棵树的边用布尔数组记录哪些节点是被标记的点。连通块遍历遍历所有节点每遇到一个未访问过的标记点就启动DFS遍历整个连通块递归仅沿着标记点延伸保证只在连通块内部遍历同时标记访问状态避免重复。遍历当前节点的所有邻居若邻居是未标记点则对应一条出口边计数加1。结果聚合每找到一个连通块最小代价加1总方案数乘以该块的出口边数全程取模。3. 复杂度分析时间复杂度O ( n ) O(n)O(n)每个节点和每条边仅被访问一次线性遍历整棵树。空间复杂度O ( n ) O(n)O(n)邻接表、标记数组与访问数组的空间开销适配十万级节点规模。总结核心逻辑免费红边将标记点划分为多个连通块每个块至少选一条出口边连接未标记区域最小代价为块的数量方案数为各块可选出口边数的乘积。关键操作标记点连通块划分、出口边逐条计数、乘法原理计算总方案数。效率保障单次DFS线性遍历无冗余计算十万级数据可毫秒级处理完成。代码简要说明全局数组定义masked[]布尔数组标记节点是否为被选中的标记点。vis[]访问标记数组用于DFS遍历连通块时去重。G[]邻接表存储树的所有无向边。DFS连通块遍历函数接收当前节点与出口边计数变量cnt引用传递直接修改外部计数。若当前节点已访问直接返回否则标记为已访问。遍历所有邻接节点若邻居是未访问的标记点递归深入扩展连通块若邻居未被访问必为未标记点说明找到一条出口边cnt自增1。主函数逻辑读入总节点数与标记点数将所有标记点对应位置标记为true。读入n-1条边构建无向邻接表。从1到n遍历所有节点每发现一个未访问的标记点启动DFS统计该连通块的出口边数最小代价加1总方案数乘以当前块的边数并对模数取余。最终按顺序输出最小代价与方案总数。输入优化关闭流同步并解绑cin与cout大幅提升十万级数据的读取与输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXN200005;boolvis[MAXN]{false};boolmasked[MAXN]{false};vectorllG[MAXN];voiddfs(ll v,llcnt){if(vis[v])return;vis[v]true;for(ll i0;i(ll)G[v].size();i){if(masked[G[v][i]]!vis[G[v][i]])dfs(G[v][i],cnt);elseif(!vis[G[v][i]])cnt;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k;cinnk;for(ll i0;ik;i){ll v;cinv;masked[v]true;}for(ll i0;in-1;i){ll u,v;cinuv;G[u].push_back(v);G[v].push_back(u);}ll ans1,cost0;for(ll i1;in;i){if(masked[i]!vis[i]){ll cnt0;dfs(i,cnt);cost;ans(ans*cnt)%mod;}}coutcost ans\n;return0;}