题目描述

小

在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。

激励电流在导线上的传播是需要花费时间的，对于每条边 $ee，激励电流通过它需要的时间为t_ete，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小QQ有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？$

输入输出格式

输入格式：

第一行包含一个正整数

第二行包含一个整数

接下来

输出格式：

仅包含一个整数

输入输出样例

输入样例#1：

311 2 11 3 3

输出样例#1：

说明

对于 $40\%40%的数据，N ≤ 1000N≤1000$

对于 $100\%100%的数据，N ≤ 500000N≤500000$

对于所有的数据， $t_e ≤ 1000000te≤1000000$

题解

首先，可以把倒过来做，也就是从终点到激发器所用的时间相同

所以以s为根搜到最下一层再往上做，再回溯的过程中记录有几条路线经过这个节点，并将其修改时间为一样的

代码

1 #include 
     
       2 #include 
      
         3 using namespace std; 4 struct edge {
   int to,from,t;}e[500010*2]; 5 int n,s,cnt,head[500010]; 6 long long a[500010*2],ans; 7 bool vis[500010]; 8 void insert(int x,int y,int z) { e[++cnt].to=y; e[cnt].from=head[x]; e[cnt].t=z; head[x]=cnt; } 9 void dfs(int d)10 {11     vis[d]=1;12     int num=0;13     for (int i=head[d];i;i=e[i].from)14         if (!vis[e[i].to])15         {16             dfs(e[i].to);17             if (a[e[i].to]+e[i].t>a[d])18             {19                 ans+=(a[e[i].to]+e[i].t-a[d])*num,num++;20                 a[d]=a[e[i].to]+e[i].t;21             }22             else ans+=a[d]-a[e[i].to]-e[i].t,num++;23         }24 }25 int main()26 {27     scanf("%d%d",&n,&s);28     for (int i=1,x,y,z;i<=n-1;i++) scanf("%d%d%d",&x,&y,&z),insert(x,y,z),insert(y,x,z);29     dfs(s);30     printf("%lld",ans);31 }

转载于:https://www.cnblogs.com/Comfortable/p/9790967.html

你可能感兴趣的文章