P1131 时态同步网页链接P1131 时态同步题目描述小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成我们不妨称之为节点并将其用数字1 , 2 , 3 ⋯ 1,2,3\cdots1,2,3⋯进行标号。电路板的各个节点由若干不相交的导线相连接且对于电路板的任何两个节点都存在且仅存在一条通路通路指连接两个元件的导线序列。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后产生一个激励电流通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后得到信息并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终激励电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。激励电流在导线上的传播是需要花费时间的对于每条边e ee激励电流通过它需要的时间为t e t_ete而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求故需要通过改变连接线的构造。目前小 Q 有一个道具使用一次该道具可以使得激励电流通过某条连接导线的时间增加一个单位。请问小 Q 最少使用多少次道具才可使得所有的“终止节点”时态同步输入格式第一行包含一个正整数N NN表示电路板中节点的个数。第二行包含一个整数S SS为该电路板的激发器的编号。接下来N − 1 N-1N−1行每行三个整数a , b , t a,b,ta,b,t。表示该条导线连接节点a aa与节点b bb且激励电流通过这条导线需要t tt个单位时间。输出格式仅包含一个整数V VV为小 Q 最少使用的道具次数。输入输出样例 #1输入 #13 1 1 2 1 1 3 3输出 #12说明/提示对于40 % 40\%40%的数据1 ≤ N ≤ 1000 1\le N\le 10001≤N≤1000。对于100 % 100\%100%的数据1 ≤ N ≤ 5 × 10 5 1\le N\le 5\times 10^51≤N≤5×105。对于所有的数据1 ≤ t e ≤ 10 6 1\le t_e\le 10^61≤te≤106。解题思路本题是树形动态规划 贪心的经典问题。给定一棵以激发器S SS为根的树每条边有传播时间t e t_ete。激励电流从根出发最终到达所有叶子节点终止节点。要求所有叶子节点同时接收到电流即从根到每个叶子的路径总时间相等。我们可以通过消耗道具来增加某条边的时间每次增加1 11单位求最少消耗的道具次数。1. 问题等价转化对于树中的任意节点u uu设其子树中所有叶子节点到u uu的路径最大时间为a [ u ] a[u]a[u]即从u uu出发到达其子树中最远叶子的时间。为了让u uu的所有叶子节点同时到达从u uu到各个子节点v vv的路径时间加上v vv到其叶子的最大时间必须统一为a [ u ] a[u]a[u]。对于每个子节点v vv边( u , v ) (u, v)(u,v)的时间为w ww则从u uu经过v vv到叶子的总时间为a [ v ] w a[v] wa[v]w。若这个值小于a [ u ] a[u]a[u]则必须通过道具将边( u , v ) (u, v)(u,v)的时间增加a [ u ] − ( a [ v ] w ) a[u] - (a[v] w)a[u]−(a[v]w)使得该分支也能达到a [ u ] a[u]a[u]。若a [ v ] w a[v] wa[v]w大于当前的a [ u ] a[u]a[u]则更新a [ u ] a [ v ] w a[u] a[v] wa[u]a[v]w并需要将之前已经处理过的兄弟分支也提升到新的a [ u ] a[u]a[u]通过增加它们对应边的时间。因此在遍历子节点时需要动态维护当前的最大时间并累加调整量。整体思路自底向上 DFS每个节点返回其子树中叶子到该节点的最大时间同时在回溯过程中计算需要增加的时间总和。2. 算法实现建图使用链式前向星存储无向树每条边记录终点to、边权dis和下一个边的指针next。DFS 后序遍历从根节点S SS开始标记已访问。对于每个未访问的子节点v vv递归调用dfs(v)。递归返回后子节点v vv的子树最大时间a[v]已知。当前边( u , v ) (u, v)(u,v)的时间为e[i].dis则从u uu经过v vv到叶子的时间为a[v] e[i].dis。维护当前节点u uu的a[u]初始为0 00和已处理子节点的计数器cnt。若a[v] e[i].dis a[u]说明新的分支更远需要将之前所有已处理的分支都提升到新的高度增加的道具数 (a[v] e[i].dis - a[u]) * cnt。更新a[u] a[v] e[i].discnt。否则当前分支较短需要增加a[u] - a[v] - e[i].dis的道具数cnt。输出答案DFS 结束后累加的总道具数ans即为最少消耗。3. 复杂度分析时间复杂度每个节点和每条边仅被访问一次DFS 为O ( N ) O(N)O(N)。N ≤ 5 × 10 5 N \le 5 \times 10^5N≤5×105完全可行。空间复杂度链式前向星存储边O ( N ) O(N)O(N)递归栈深度最坏O ( N ) O(N)O(N)数组a aa和vis均为O ( N ) O(N)O(N)。总空间O ( N ) O(N)O(N)满足限制。总结本题的核心是让所有叶子节点同时收到信号等价于让每个节点的所有分支到叶子的最大时间一致。通过自底向上的 DFS动态维护当前子树的最大时间并在遇到更远分支时将之前较短的分支统一“拉长”到新高度。每次拉长所需增加的时间即为道具消耗。算法直观且高效是树形贪心的典型应用。代码简要说明链式前向星head[]存头指针e[]存边信息to,next,disnum为边计数。数组a[N]a[u]表示以u uu为根的子树中叶子到u uu的最大路径时间边权之和。数组vis[N]标记节点是否已访问避免重复遍历。dfs(u)函数标记vis[u] 1。初始化cnt 0。遍历u的所有邻边若邻点未访问递归dfs(to)。计算tmp a[to] e[i].dis。若tmp a[u]则ans (tmp - a[u]) * cnt更新a[u] tmp。否则ans a[u] - tmp。cnt。主函数读入N , S N, SN,S建图调用dfs(S)输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N504561;constll INF1e18;constll M1e610;constll mod1e97;ll head[N*2];ll a[N*2];ll n,m,s,num;ll ans0;boolvis[N];structpoint{ll to,next,dis;}e[N*2];voidadd(ll from,ll to,ll dis){e[num].nexthead[from];e[num].toto;e[num].disdis;head[from]num;}voiddfs(ll u){vis[u]1;ll cnt0;for(ll ihead[u];i!0;ie[i].next){ll toe[i].to;if(!vis[to]){dfs(to);if(a[to]e[i].disa[u]){ans(a[to]e[i].dis-a[u])*cnt;cnt;a[u]a[to]e[i].dis;}else{ansa[u]-a[to]-e[i].dis;cnt;}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,s);for(ll i1;in;i){ll x,y,z;scanf(%lld%lld%lld,x,y,z);add(x,y,z);add(y,x,z);}memset(vis,0,sizeof(vis));dfs(s);printf(%lld,ans);return0;}