树的遍历
2026-01-31 10:22:51
发布于：四川
1阅读
0回复
0点赞
//树的遍历
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const int maxn=2e6+5; // 开2e6+5适配双向边存储（n≤1e6时边数≤2e6）
ll n,m; // n：节点数
int head[maxn],node; // head[u]：节点u的邻接表头；node：边的计数（链式前向星）
// 链式前向星的边结构体
struct Edge{
ll v,w,pre; // v：边的终点；w：边长度；pre：上一条边的下标
}edge[maxn];
// 快速添加双向边的函数（链式前向星）
inline void add_edge(int u,int v,ll w){
edge[++node].v=v; // 新增边的终点为v
edge[node].w=w; // 边长度为w
edge[node].pre=head[u]; // 指向当前u的头边
head[u]=node; // 更新u的头边为新增边
}
ll ans=0; // 总费用（需用long long避免溢出）
ll son[maxn]; // son[u]：以u为根的子树节点数
// 深度优先搜索：统计子树节点数并计算边费用
// u：当前节点；f：父节点（避免回边）
void dfs(int u,int f){
son[u]=1; // 初始时子树只有当前节点u
// 遍历u的所有邻接边
for(register int i=head[u];i;i=edge[i].pre){
int v=edge[i].v; // 边的终点v
if(f!=v){ // 跳过父节点，避免递归回退
dfs(v,u); // 递归遍历子节点v，父节点为u
son[u]+=son[v]; // 累加v的子树节点数到u的子树
// 计算当前边的费用：长度 × |(n-son[v]) - son[v]| = 长度 × |n - 2*son[v]|
ans+=abs((n-son[v])-son[v])*edge[i].w;
}
}
}
signed main(){
ios,tie; // 关闭同步，加速输入输出
ll u,v,w;
cin>>n; // 输入节点数
// 读取n-1条边，构建双向邻接表
for(register int i=1;i<n;++i){
cin>>u>>v>>w;
add_edge(u,v,w); // 添加u→v的边
add_edge(v,u,w); // 添加v→u的边（双向）
}
dfs(1,0); // 从根节点1开始DFS，父节点为0（无）
cout<<ans<<endl; // 输出总费用
return 0;
}
这里空空如也
有帮助，赞一个