【问题描述】

树型网络是最节省材料的网络。所谓树型网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。

网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。如图6-4，server结点发出一个信号给结点a和c，a再转发给b。如此，整个网络都收到这个信号了。

server            a          b
   ●-------------○----------○
   │
   │
   ○

但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。衰减量一般由线路长度决定。

server       3    a    2     b
   ●-------------○----------○
   │
   │1
   ○

如上图，边上所标的数字为边的衰减量。假设从server出发一个强度为4个单位的信号，发到结点a后强度衰减为4-3=1个单位。结点a再将其转发给结点b。由于信号强度为1，衰减量为2，因此信号无法发送到b。

一个解决这一问题的方法是，安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度）。

上图中，若在结点a处安装一个信号放大器，则强度为4的信号发到a处，即被放大至4。这样，信号就可以被发送的网络中的任意一个节点了。为了简化问题，我们假定每个结点只处理一次信号，当它第二次收到某个信号时，就忽略此信号。

你的任务是根据给出的树型网络，计算出最少需要安装的信号放大器数量。

【输入】

第一行一个整数n，表示网络中结点的数量。（n<=100000）

第2~n+1行，每行描述一个节点的连接关系。其中第i+1行，描述的是结点i的连接关系：首先一个整数k，表示与结点i相连的结点的数量。此后2k个数，每两个描述一个与结点i相连的结点，分别表示结点的编号（编号在1~n之间）和该结点与结点i之间的边的信号衰减量。结点1表示服务器。

最后一行，一个整数，表示从服务器上出发信号的强度。

【输出】

一个整数，表示要使信号能够传遍整个网络，需要安装的最少的信号放大器数量。

如果不论如何安装信号放大器，都无法使信号传遍整个网络，则输出“No solution.”

【样例输入】

4                       

2 2 3 3 1

2 1 3 4 2

1 1 1

1 2 2

4

【样例输出】

1

 对于任意一个信号放大器安装，如果安装在离根较近的点可以且安装在离根较远的点也可以的话，则这个信号放大器安装在离根较近的点会更优，因为离根较近的点的影响范围比较大。

依此，我们可以从叶结点开始贪心，记录每个结点传遍其子树所需的信号f[i](在满足安装最少信号放大器的条件下)，并且记录所有叶结点所需信号为1。

可以得出递推式f[i]=max(f[j]+dis[i][j]); j∈i结点的子结点的集合

若有子结点的所需信号加上到当前结点的边权大于服务器发出的信号则在这个子结点上安装一个信号放大器（因为当前结点不可能发出大于服务器信号的信号，不存在将子树装了一个信号放大器还不满足条件的情况，因为在处理子树的时候已经解决了这种情况），并将其所需的信号改为1。

无解的情况只存在于有边的权大于等于服务器发出的信号。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define R register
 4 #define N 100007
 5 
 6 struct info{
 7   int pre,to,dis;
 8 }edge[2*N];
 9 
10 int n,size,ans,signal,head[N],f[N],fa[N];
11 
12 void addline(int from,int to,int dis){
13   edge[++size].pre=head[from];head[from]=size;
14   edge[size].to=to;edge[size].dis=dis;
15 }
16 
17 void tsdp(int k){
18   f[k]=1;
19   for (R int i=head[k];i;i=edge[i].pre)
20   if (fa[k]!=edge[i].to){
21     fa[edge[i].to]=k;
22     tsdp(edge[i].to);
23     int t=f[edge[i].to]+edge[i].dis;
24     if (t<=signal) f[k]=std::max(f[k],t);
25     else ++ans,f[k]=std::max(f[k],1+edge[i].dis);
26   }
27 }
28 
29 int main(){
30   freopen("booster.in","r",stdin);
31   freopen("booster.out","w",stdout);
32   scanf("%d",&n);
33   for (R int i=1;i<=n;++i){
34     int k;scanf("%d",&k);
35     for (R int j=1;j<=k;++j){
36       int to,dis;
37       scanf("%d%d",&to,&dis);
38       addline(i,to,dis);
39     }
40   }
41   scanf("%d",&signal);
42   for (R int i=1;i<=size;++i)
43   if (edge[i].dis>=signal){
44     printf("No solution.");
45     return 0;
46   }
47   tsdp(1);
48   printf("%d",ans);
49   return 0;
50 }

信号放大器【贪心】