本文共 2880 字，大约阅读时间需要 9 分钟。

更好的观看体验：

因为做之前不知道树形dp，所以这道题当时自己的想法只有floyd，骗了48分。这里附上floyd的超时代码

说下自己当时写了这代码但是debug好久，原因时这是个无向图，需要两边建边，只有一边肯定是出问题的

#include 
   
    #include
    
     #include
     
      using namespace std;const int N = 2010, INF =0x3f3f3f ;int n, m, k, x, y;int d[N][N];int a[N];void floyd() {    for(int k = 1; k <= n; k++)        for(int i = 1; i <= n; i++)            for(int j = 1; j <= n; j++)                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}int main() {	cin.tie(0);std::ios::sync_with_stdio(false);    cin>>n;    for(int i=1;i<=n;i++)    {    	cin>>a[i];	}    m=n-1;    //初始化     for(int i = 1; i <= n; i++)        for(int j = 1; j <= n; j++)            if(i == j) d[i][j] = 0;            else d[i][j] = INF;    while(m--) {        cin >> x >> y ;        d[x][y] = min(d[x][y],1);        d[y][x]=min(d[y][x],1);        //注意保存最小的边    }        floyd();    	int res=-1;	for(int i=1;i<=n;i++)	{		for(int j=1;j<=n;j++)		{			if(i!=j&&a[i]>a[j]&&d[i][j]
     
    
   

那正确的思路是什么呢?

我们要在{ax,ay}*dis[x,y]的所有情况中找一个最大的

等价求MAX{(ax,ay)*dis[x,y]} 由于ax,ay不管哪个大哪个小支付的总是max(ax,ay)*dis[x,y]，他们的最短路是公共的一样长的。所以我们不妨以ax为研究对象，找max{ax*dis[x,y]}.

ax是我们输入的每个村庄的疫情情况，所有我们找max{dis[x,y]}。而如果我们了解树的直径就知道在树上离x，最远的点只会是树直径的端点中的一个.

我们先对最远的点只会是树的直径的端点中的一个进行证明。

反证法：假设cd是树的直径,假如1>=2,那么1+3>=2+3,而树的直径的定义是树上两点距离最长的点，不会存在有1+3这样严格>2+3(直径)的新的直径，和原命题矛盾。另一种1和3的情况同理。综上， 在树上离x，最远的点只会是树直径的端点中的一个。

讲到了这，那么树的直径怎么求呢？本题是树形dp的一个经典问题，即每条边的权重都是1，有一种解法是dfs解法，适用于边权为正的情况

思路：先用dfs求离随意一个点的最远点(c)，然后再用最远点(c)求另一个离c最远的最远点(d),cd就是树的直径，cd分别是两端点

我们来对这个求直径的方法进行证明：我们还是用反证法

任取一点a，离a最远点为u，证u一定是某一条直径的一个端点，那么从u出发最远的点连起来就是直径

我们先证明两条路径没有交点的情况（另一个交点为y，1是ux)

由于连通，那么au可以从x走出通过y然后到b或者c;

因为u是到a最远的一个点,所以从a点到c的距离和a到u的距离减去公共部分可以得到: 1>=2+4,则可以推出1+2>=4.

那么从b出发，沿着1-2走的距离>=4,即3+1+2>=3+4,又因为3+4是树的直径,所以我们找到了和bc起码一样长的路径，从而u是直径的一个端点.那么显然离u最远的一个点就是直径的另一个端点

case2:有交点的情况

因为u是距离a最远的一个点,所以au>=ac,从而1>=2,所以b->u>=b->c，又因为bc是直径,从而u是某一条直径的端点。 那么显然离u最远的一个点就是直径的另一个端点.

那么理解了之后代码板子怎么写呢

这是标程

#include 
   
    #define clr(x) memset(x,0,sizeof (x))#define For(i,a,b) for (int i=(a);i<=(b);i++)#define Fod(i,b,a) for (int i=(b);i>=(a);i--)#define fi first#define se second#define pb(x) push_back(x)#define mp(x,y) make_pair(x,y)#define outval(x) cerr<<#x" = "<
    
     <
    
   

这是最后我理解了写出的代码，虽然不那么简洁，但是我觉得方便理解

• 如果程序找找自己的vis两次是否清空

• 关于dfs有个地方要说：因为是树的结构所以每一个搜到的节点都是终点，无需回溯

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;int const maxn=50010;int n;LL a[maxn];LL dx[maxn],dy[maxn];LL vis[maxn];dx[] 存ai到直径第二个端点的距离//dy[] 存ai到直径第一个端点的距离vector
       
        e[maxn];//指针指向数组的第一个元素地址,这么写方便调用函数，不用再主函数再写一个for void dfs(int x,LL *d){	vis[x]=1;///dfs容易忘的标记 	for(int i=0;i
        
         >n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n-1;i++) { int x;int y; cin>>x>>y; e[x].push_back(y);//无向图存储，若是有权树还要用结构体 e[y].push_back(x); } //先找到直径的一个端点 dfs(1,dx); int res=0;int q=0;//q表示直径的第一个端点 for(int i=1;i<=n;i++) { if(res
        
       
      
     
    
   

转载地址：http://qsdt.baihongyu.com/