P1131题解

问题：
有一个树形结构的电路板，其中有一个激发器（根节点），电流从根节点出发，沿着树边传播到所有叶子节点（终止节点）。每条边有一个传播时间，我们需要通过增加某些边的传播时间，使得所有叶子节点同时接收到电流。
解法：
贪心：
从叶子节点开始向上处理
对于每个节点，计算从其到其子树中叶子节点的最大路径长度
对于节点的每个子节点，将它们的路径长度补齐到这个最大值
向上传递时，加上当前节点到父节点的边权
算法：
使用BFS或DFS建立树结构（因为N很大，需要避免递归深度过大）
通过拓扑排序（从叶子到根）处理节点
对于每个节点：
找到所有子节点中的最大f[y]+w（即最大路径长度）
将所有子节点的路径长度补齐到这个最大值
当前节点的f[x]=这个最大值
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int h[N],v[N<<1],nxt[N<<1],cnt,d[N<<1];
long long res,f[N];
int q[N],fa[N];
void add(int x,int y,int z)
{
v[++cnt]=y;
d[cnt]=z;
nxt[cnt]=h[x];
h[x]=cnt;
}
int main()
{
int n,st;
scanf("%d%d",&n,&st);

for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
int l=0,r=0;
q[0]=st;
fa[st]=0;
while(l<=r)
{
int x=q[l++];
for(int i=h[x];i;i=nxt[i])
{
int y=v[i];
if(y==fa[x]) continue;
fa[y]=x;
q[++r]=y;
}
}
for(int i=r;i>=0;i--)
{
int x=q[i];
long long mx=0;
for(int j=h[x];j;j=nxt[j])
{
int y=v[j],w=d[j];
if(y==fa[x]) continue;
f[x]=max(f[x],f[y]+w);
}
for(int j=h[x];j;j=nxt[j])
{
int y=v[j],w=d[j];
if(y==fa[x]) continue;
res+=f[x]-(f[y]+w);
}
}
printf("%lld\n",res);
return 0;
}