上海招标网站,科技股龙头,wordpress阿里云esc配置,seo搜索引擎优化是做什么的hdu 2196 题意 给出一棵树#xff0c;求出树上每一个点在树上走一条简单路径所能走的最长距离。 解法 说起来#xff0c;这是我今天1A的第一题 我们设\(up[i]\) 表示从这个点向上走到某个点又向下走的最长距离 设 \(down[i][0]\) 表示从这个点出发向他的子树所能走到的最大距…hdu 2196 题意 给出一棵树求出树上每一个点在树上走一条简单路径所能走的最长距离。 解法 说起来这是我今天1A的第一题 我们设\(up[i]\) 表示从这个点向上走到某个点又向下走的最长距离 设 \(down[i][0]\) 表示从这个点出发向他的子树所能走到的最大距离\(down[i][1]\) 表示从这个点出发向他的子树所能走到的次大距离 然后我们就可以愉快的开始转移了。 我们先dfs一边求出 \(down[i][0/1]\) 然后我们再dfs一边求 \(up[i]\) 。 首先 \(up[i] up[fa] dis[i][fa]\) 如果 i 在 fa 向下走的最深路径上那么 \(up[i] max(up[i],dis[i][fa]down[fa][1])\) 否则 \(up[i] max(up[i],dis[i][fa]down[fa][0])\) 最后每个点的答案为 \(max(up[i],down[i][0])\) 。 代码 #include iostream
#include cstdio
#include cstdlib
#include cstring
#include cmath
#include algorithm
#include cctype
#include vector
#define INF 2139062143
#define MAX 0x7ffffffffffffff
#define del(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
templatetypename T
inline void read(Tx)
{x0;T k1;char cgetchar();while(!isdigit(c)){if(c-)k-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}x*k;
}
const int maxn100005;
int up[maxn];
int down[maxn][2];
int n;
struct Edge{int u,v,w;Edge(int u0,int v0,int w0):u(u),v(v),w(w){}
};
vectorEdge edge;
vectorint G[maxn];
void add_edge(int u,int v,int w) {edge.push_back(Edge(u,v,w));edge.push_back(Edge(v,u,w));int medge.size();G[u].push_back(m-2);G[v].push_back(m-1);
}void dfs1(int u,int fa) {for(int i0;iG[u].size();i) {Edge eedge[G[u][i]];int ve.v;if(vfa) continue;dfs1(v,u);if(down[v][0]e.wdown[u][0]){down[u][1]down[u][0];down[u][0]down[v][0]e.w;}else if(down[v][0]e.wdown[u][1]) down[u][1]down[v][0]e.w;}
}
void dfs2(int u,int fa) {for(int i0;iG[u].size();i) {Edge eedge[G[u][i]];int ve.v;if(vfa) continue;if(down[u][0]!down[v][0]e.w)up[v]e.wdown[u][0];else up[v]e.wdown[u][1];up[v]max(up[u]e.w,up[v]);dfs2(v,u);}
}
void _init() {edge.clear();for(int i1;in;i) G[i].clear();del(down,0);del(up,0);
}
int main()
{while(~scanf(%d,n)){_init();for(int u2,v,w;un;u) {read(v);read(w);add_edge(u,v,w);}dfs1(1,1);dfs2(1,1);for(int i1;in;i) printf(%d\n,max(up[i],down[i][0]));}return 0;
} 转载于:https://www.cnblogs.com/mrasd/p/9550879.html
