2017年4月4日考试总结

考试总结"/>

2017年4月4日考试总结

第一题：最长链

题目描述：给定一棵有n个节点的树，求每个节点到其他节点的最大距离

输入：第一行是一个自然数n(n≤10000),接下来 (n−1)行描述： 第i行包含两个自然数, 表示编号为i的节点连接到的节点编号和这条网线的长度..距离总长不会超过10^9.每行中的两个数字用空格隔开.

输出：包含n行.第i行表示对于离编号为i的节点最远的节点与该节点的距离Si(1≤i≤n).

成绩：AC

题解：g[x][0]和g[x][1]表示以1为根的树中，x子树中的最长链和次长链（不能有相同的边）dp[x][0],dp[x][1]表示整棵树中过x的最远距离和次远距离（也不能有相同的边）。

（方程式情况难以描述，就不打了23333333）

P.s：法二：树的直径。

分析：前一天刚讲过，还是写得很快的~\(≧▽≦)/~啦啦啦。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
const int N=10000+10;
inline void getint(int&num){char c;int flag=1;num=0;while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}num*=flag;
}
struct bian{int v,w,next;
}arr[N<<1];
int n,a,w,cnt,fir[N],g[N][2],dp[N][2],tmp[7];
inline void link(int a,int b,int w){arr[++cnt].v=a,arr[cnt].w=w;arr[cnt].next=fir[b],fir[b]=cnt;
}
void work(int x,int pre){for(int i=fir[x];i;i=arr[i].next)if(arr[i].v!=pre){work(arr[i].v,x);if(g[arr[i].v][0]+arr[i].w>g[x][0])g[x][1]=g[x][0],g[x][0]=g[arr[i].v][0]+arr[i].