长春做网站设计,南京网络推广建站,百度推广运营专员,怎么提高网站的百度收录树的直径即为一棵树中距离最远的两点之间的路径
方法一#xff1a;DFS
先以任意一点为起点跑一遍dfs#xff0c;记录离起点距离最远的点p#xff08;这个点一定是直径的一个端点#xff0c;感性理解一下不证明了#xff09;#xff0c;然后再以最远点再跑一遍dfs#…树的直径即为一棵树中距离最远的两点之间的路径
方法一DFS
先以任意一点为起点跑一遍dfs记录离起点距离最远的点p这个点一定是直径的一个端点感性理解一下不证明了然后再以最远点再跑一遍dfs记录此时距离最远的点q那么pq就是该树的直接
树中有负权边时不可以用这个方法
const int N 10000 10;int n, c, d[N];
vectorint g[N];void dfs(int u, int fa)
{for (int v : E[u]){if (v fa) continue;d[v] d[u] 1; // 如边有权值把1换成权值即可if (d[v] d[c]) c v; // 更新最大距离的点dfs(v, u);}
}int main()
{cin n;for (int i 1; i n; i){int u, v;scanf(%d %d, u, v);g[u].push_back(v), g[v].push_back(u);}dfs(1, 0); // 第一遍dfsint p c; // 一个端点d[c] 0;dfs(c, 0); // 第二遍dfsint q c; // 另一个端点cout d[c];return 0;
}方法二树形dp
dp[u]为以u为根的子树中离u最远的点的路径长度 转移方程v为u的子结点dp[u] max(dp[u], dp[v] w(u, v)) 两条经过根结点的最长路径即为该子树中的直径 转移方程zj max(zj, dp[u] dp[v] w(u, v))
const int N 10000 10;int n, zj 0;
int dp[N];
vectorint g[N];void dfs(int u, int fa)
{for (int v : E[u]){if (v fa) continue;dfs(v, u);zj max(zj, dp[u] dp[v] 1); // 如为有权边把1换成权值即可dp[u] max(dp[u], dp[v] 1); // 如为有权边把1换成权值即可}
}int main()
{cin n;for (int i 1; i n; i){int u, v;cin u v;g[u].push_back(v), g[v].push_back(u);}dfs(1, 0);cout zj \n;return 0;
}
