首页 > 代码库 > SGU149 Computer Network

SGU149 Computer Network

题解:

与树的路径有关的题目,挺赞的一道题目

首先树的一个节点,他的最远点,要么在他的子树,要么在他的父节点的子树中

那么我们先求出每个节点的子树中的最远点和次远点。然后求父节点的中的最远点。

在父节点中,如果该点不在父节点的最远路径上,那么该父节点的最远点则是最优的,否则次远点是最优的

但是不知道如何实现啊。。。。。。看了别人的代码

代码:

#include<iostream>#include<cstdio>#include<vector>#include<cstring>#include<cmath>#include<queue>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=10100;const int mod=1e9+7;int First_son[maxn],Second_son[maxn],First_fa[maxn];int First_son_point[maxn];struct Edge{    int to,nxt,w;}edge[maxn*2];int head[maxn],p[maxn];int cnt,n,u,w;void addEdge(int u,int v,int w){    edge[cnt].to=v;    edge[cnt].w=w;    edge[cnt].nxt=head[u];    head[u]=cnt++;}//将无根树化为有根树,根为1 void dfs(int u,int fa){    p[u]=fa;    for(int i=head[u];i!=-1;i=edge[i].nxt){        int v=edge[i].to;        if(v!=fa) dfs(v,u);    }}//找子树中的最远节点和次远节点,因为是子树,是从下到上更新,先dfs1 void dfs1(int u){    First_son[u]=Second_son[u]=0;    for(int i=head[u];i!=-1;i=edge[i].nxt){        int v=edge[i].to;        if(v==p[u]) continue;        dfs1(v);        if(Second_son[u]<First_son[v]+edge[i].w){            Second_son[u]=First_son[v]+edge[i].w;            if(First_son[u]<Second_son[u]){                First_son_point[u]=v;                swap(First_son[u],Second_son[u]);            }        }    }}//找寻父节点中的最远节点,是从上到下,所以是后dfs2 void dfs2(int u){    for(int i=head[u];i!=-1;i=edge[i].nxt){        int v=edge[i].to;        if(v==p[u]) continue;        if(v==First_son_point[u]) First_fa[v]=edge[i].w+max(Second_son[u],First_fa[u]);        else                      First_fa[v]=edge[i].w+max(First_son[u],First_fa[u]);        dfs2(v);    }}int main(){    cnt=0;    memset(head,-1,sizeof(head));    scanf("%d",&n);    for(int v=2;v<=n;v++){        scanf("%d%d",&u,&w);        addEdge(u,v,w);        addEdge(v,u,w);    }    dfs(1,-1);    dfs1(1);    dfs2(1);    for(int i=1;i<=n;i++) printf("%d\n",max(First_son[i],First_fa[i]));    return 0;}

 

SGU149 Computer Network