可以知道，要使XY+YZ最大，XYZ三点都应该为树的叶节点(X可能特殊)。XYZ位置应该是一个三叉状，如下图所示。

Z
|
P--Y
|
X

假设XY,YZ路径交点(分离点)为P，则限制条件|XY|<=|XZ|可以化为|XP|+|YP| <= |XP|+|ZP|，进而得出|YP|<=|ZP|。而我们要求最大化的|XY|+|YZ|则为|XP|+2|YP|+|ZP|。设 S=|XP|+2|YP|+|ZP|。要想使S最大，应在|ZP|确定时尽量使|XP|+2|YP|最大，而|XP|和|YP|属于P的两棵不同的子树，所以应该尽量让|YP|最大，|XP|<=|YP|。于是可以得出约束条件|XP|<=|YP|<=|ZP|。

对于确定的P，S的值就是P的路径长度前三大的子树的路径长度之和。于是问题就转化为了在树中找到一个点P，使得由P出发相交与P点的三条路径长度值和的最大，求出最大值。分析到这里，这个问题就可以用很简单的动态规划解决了。首先求出每棵子树中从根出发的最长路径的长度，记做H[i] (以i为根的子树)。接下来，再次从根节点出发，求出到每个节点的前三大的路径，特殊地X可以与P重合(也就是求前两大路径)。路径可以是子树之间过根节点互联，也可以是与根节点的父节点相连。

时间复杂度为O(N)。

这道题我居然找到了两个版本，不知哪个是正宗的！？“数据生成器”还是“逃学的小孩”？

/* 
 * Problem: NOI2003 jerrygen
 * Author: Guo Jiabao
 * Time: 2009.5.23 14:20
 * State: Solved
 * Memo: 贪心 + 树形动态规划
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=200001,MAXM=MAXN*2;
using namespace std;
typedef long long Big;
struct edge
{
	edge *next;
	int t; Big c;
}ES[MAXM],*V[MAXN];
int N,M,EC;
Big H[MAXN],Ans;
inline void addedge(int a,int b,Big c)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b; V[a]->c=c;
	ES[++EC].next=V[b];
	V[b]=ES+EC; V[b]->t=a; V[b]->c=c;
}
void init()
{
	int i,a,b,c;
	freopen("jerrygen.in","r",stdin);
	freopen("jerrygen.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<N;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
}
void CalcHeight(int i)
{
	H[i]=0;
	for (edge *e=V[i];e;e=e->next)
	{
		int j=e->t;
		if (H[j]==-1)
		{
			CalcHeight(j);
			if (H[j] + e->c > H[i])
				H[i] = H[j] + e->c;
		}
	}
}
void GetMaxChild(int i,int f,Big fl,int *M,Big *Max)
{
	Max[0]=Max[1]=Max[2]=M[0]=M[1]=M[2]=-1;
	Max[0]=fl; M[0]=f;
	for (edge *e=V[i];e;e=e->next)
	{
		int j=e->t;
		if (j!=f)
		{
			if (H[j] + e->c > Max[0])
			{
				Max[2]=Max[1];M[2]=M[1];
				Max[1]=Max[0];M[1]=M[0];
				Max[0] = H[j] + e->c;
				M[0] = j;
			}
			else if (H[j] + e->c > Max[1])
			{
				Max[2]=Max[1];M[2]=M[1];
				Max[1] = H[j] + e->c;
				M[1] = j;
			}
			else if (H[j] + e->c > Max[2])
			{
				Max[2] = H[j] + e->c;
				M[2] = j;
			}
		}
	}
}
void DP(int i,int f,Big fl)
{
	int M[3],j;
	Big Max[3],A,C;
	if (i==97)
		j=1;
	GetMaxChild(i,f,fl,M,Max);
	if (M[1]==-1)
		return;
	else if (M[2]==-1)
	{
		if (V[i]->t==f) V[i]=V[i]->next;
		j=V[i]->t;
		A=Max[0] + Max[1]*2;
		if (A>Ans)
			Ans=A;
		C=fl + V[i]->c;
		DP(j,i,C);
	}
	else
	{
		A=Max[0] + Max[1]*2 + Max[2];
		if (A>Ans)
			Ans=A;
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (j==f) continue;
			if (M[0]==j)
				C = Max[1] + e->c;
			else
				C = Max[0] + e->c;
			DP(j,i,C);
		}
	}
}
void solve()
{
	for (int i=1;i<=N;i++)
		H[i]=-1;
	CalcHeight(1);
	DP(1,0,0);
}
int main()
{
	init();
	solve();
	cout << Ans << endl;
	return 0;
}

<h2><span class="mw-headline">数据生成器 </span></h2>

【题目背景】

小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了，于是对原题做了一些扩展：

将原题的N从20扩展到200000。
将原题经过一条街道需要的时间改为Ti（1 <= Ti <= 1000000000）分钟（i为街道的编号）。
增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。

即使这样，他仍然很快地做了出来。于是，小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。

【小明扩展的题目（注意，你并不需要解决此题）】

幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y（因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离），再到大狗家Z，将两份礼物取回。卡通城由N（3 <= N <= 200000）个居住点和N-1条连接居住点的双向街道组成，经过第i条街道需花费Ti（1 <= Ti <= 1000000000）分钟的时间。可以保证，任两个居住点间都存在通路。

不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？

【任务描述】

定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。

给出卡通城的地图，找到一组X、Y、Z，使得：
|XY|≤|XZ|
|XY|+|YZ|最大。

并求出此时|XY|+|YZ|的值。

【输入文件】

输入文件第一行是两个整数N（3 £ N £ 200000）和M（M=N-1），分别表示居住点总数和街道总数。从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、 Ti（1£Ui, Vi £ N，1 £ Ti £ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。

【输出文件】

输出文件仅包含一个整数T，即|XY|+|YZ|的最大值。

【样例输入】
```
4 3
  1 2 1
  2 3 1
  3 4 1
```
【样例输出】
```
4
```

附：

《逃学的小孩》

<h2><span>【问题描述】</span></h2>

<p class="MsoNormalIndent"><span lang="EN-US">Chris</span><span>家的电话铃响起了，里面传出了</span><span lang="EN-US">Chris</span><span>的老师焦急的声音：“喂，是</span><span lang="EN-US">Chris</span><span>的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，</span><span lang="EN-US">Chris</span><span>的父母就心急如焚，他们决定在尽量短的时间内找到</span><span lang="EN-US">Chris</span><span>。他们告诉</span><span lang="EN-US">Chris</span><span>的老师：“根据以往的经验，</span><span lang="EN-US">Chris</span><span>现在必然躲在朋友</span><span lang="EN-US">Shermie</span><span>或</span><span lang="EN-US">Yashiro</span><span>家里偷玩《拳皇》游戏。现在，我们就从家出发去找</span><span lang="EN-US">Chris</span><span>，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。</span></p>
<p class="MsoNormalIndent"><span lang="EN-US">Chris</span><span>居住的城市由</span><em><span lang="EN-US">N</span></em><span>个居住点和若干条连接居住点的双向街道组成，经过街道</span><em><span lang="EN-US">x</span></em><span>需花费</span><em><span lang="EN-US">T<sub>x</sub></span></em><span>分钟。可以保证，任两个居住点间有且仅有一条通路。</span><span lang="EN-US">Chris</span><span>家在点</span><span lang="EN-US">C</span><span>，</span><span lang="EN-US">Shermie</span><span>和</span><span lang="EN-US">Yashiro</span><span>分别住在点</span><span lang="EN-US">A</span><span>和点</span><span lang="EN-US">B</span><span>。</span><em><span><span lang="EN-US">Chris</span></span></em><em><span><span>的老师和</span><span lang="EN-US">Chris</span></span></em><em><span><span>的父母都有城市地图，但</span><span lang="EN-US">Chris</span></span></em><em><span><span>的父母知道点</span><span lang="EN-US">A</span></span></em><em><span><span>、</span><span lang="EN-US">B</span></span></em><em><span><span>、</span><span lang="EN-US">C</span></span></em><em><span><span>的具体位置而</span><span lang="EN-US">Chris</span></span></em><em><span><span>的老师不知</span></span></em><span>。</span></p>
<p class="MsoNormalIndent"><span>为了尽快找到</span><span lang="EN-US">Chris</span><span>，</span><span lang="EN-US">Chris</span><span>的父母会遵守以下两条规则：</span></p>
<p class="MsoNormalIndent"><span lang="EN-US"> </span></p>
<p class="MsoNormalIndent"><!--[if !supportLists]--><span lang="EN-US"><span>l<span> </span></span></span><!--[endif]--><span>如果</span><span lang="EN-US">A</span><span>距离</span><span lang="EN-US">C</span><span>比</span><span lang="EN-US">B</span><span>距离</span><span lang="EN-US">C</span><span>近，那么</span><span lang="EN-US">Chris</span><span>的父母先去</span><span lang="EN-US">Shermie</span><span>家寻找</span><span lang="EN-US">Chris</span><span>，如果找不到，</span><span lang="EN-US">Chris</span><span>的父母再去</span><span lang="EN-US">Yashiro</span><span>家；反之亦然。</span></p>
<p class="MsoNormalIndent"><!--[if !supportLists]--><span lang="EN-US"><span>l<span> </span></span></span><!--[endif]--><span lang="EN-US">Chris</span><span>的父母总沿着两点间唯一的通路行走。</span></p>
<p class="MsoNormalIndent"><span lang="EN-US"> </span></p>
<p class="MsoNormalIndent"><span>显然，</span><span lang="EN-US">Chris</span><span>的老师知道</span><span lang="EN-US">Chris</span><span>的父母在寻找</span><span lang="EN-US">Chris</span><span>的过程中会遵守以上两条规则，但由于他并不知道</span><span lang="EN-US">A</span><span>，</span><span lang="EN-US">B</span><span>，</span><span lang="EN-US">C</span><span>的具体位置，所以现在他希望你告诉他，最坏情况下</span><span lang="EN-US">Chris</span><span>的父母要耗费多长时间才能找到</span><span lang="EN-US">Chris</span><span>？</span></p>
<p class="MsoNormalIndent" align="center"><span lang="EN-US"><!--[if gte vml 1]><v:shapetype id="_x0000_t75"  coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe"  filled="f" stroked="f"> <v:stroke joinstyle="miter" /> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0" /> <v:f eqn="sum @0 1 0" /> <v:f eqn="sum 0 0 @1" /> <v:f eqn="prod @2 1 2" /> <v:f eqn="prod @3 21600 pixelWidth" /> <v:f eqn="prod @3 21600 pixelHeight" /> <v:f eqn="sum @0 0 1" /> <v:f eqn="prod @6 1 2" /> <v:f eqn="prod @7 21600 pixelWidth" /> <v:f eqn="sum @8 21600 0" /> <v:f eqn="prod @7 21600 pixelHeight" /> <v:f eqn="sum @10 21600 0" /> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" /> <o:lock v:ext="edit" aspectratio="t" /> </v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:3in;  height:2in' o:ole=""> <v:imagedata src="file:///C:DOCUME~1CMYKRG~1LOCALS~1Tempmsohtmlclip1�1clip_image001.emz" mce_src="file:///C:DOCUME~1CMYKRG~1LOCALS~1Tempmsohtmlclip1�1clip_image001.emz"   o:title="" /> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--><!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Word.Picture.8" ShapeID="_x0000_i1025"   DrawAspect="Content" ObjectID="_1304617266"> </o:OLEObject> </xml><![endif]--></span></p>
<p class="MsoNormalIndent"><span>例如上图，这座城市由</span><span lang="EN-US">4</span><span>个居住点和</span><span lang="EN-US">3</span><span>条街道组成，经过每条街道均需花费</span><span lang="EN-US">1</span><span>分钟时间。假设</span><span lang="EN-US">Chris</span><span>住在点</span><span lang="EN-US">C</span><span>，</span><span lang="EN-US">Shermie</span><span>住在点</span><span lang="EN-US">A</span><span>，</span><span lang="EN-US">Yashiro</span><span>住在点</span><span lang="EN-US">B</span><span>，因为</span><span lang="EN-US">C</span><span>到</span><span lang="EN-US">B</span><span>的距离小于</span><span lang="EN-US">C</span><span>到</span><span lang="EN-US">A</span><span>的距离，所以</span><span lang="EN-US">Chiris</span><span>的父母会先去</span><span lang="EN-US">Yashiro</span><span>家寻找</span><span lang="EN-US">Chris</span><span>，一旦找不到，再去</span><span lang="EN-US">Shermie</span><span>家寻找。这样，最坏情况下</span><span lang="EN-US">Chris</span><span>的父母需要花费</span><span lang="EN-US">4</span><span>分钟的时间才能找到</span><span lang="EN-US">Chris</span><span>。</span></p>


<h2><span>【输入文件】</span></h2>

<p class="MsoNormalIndent"><span>输入文件</span><span lang="EN-US">hookey.in</span><span>第一行是两个整数</span><em><span lang="EN-US">N</span></em><span>（</span><span lang="EN-US">3 </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>N</em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> 200000</span><span>）和</span><em><span lang="EN-US">M</span></em><span>，分别表示居住点总数和街道总数。以下</span><em><span lang="EN-US">M</span></em><span>行，每行给出一条街道的信息。第</span><em><span lang="EN-US">i+1</span></em><span>行包含整数</span><em><span lang="EN-US">U<sub>i</sub></span></em><span>、</span><em><span lang="EN-US">V<sub>i</sub></span></em><span>、</span><em><span lang="EN-US">T<sub>i</sub></span></em><span>（</span><span lang="EN-US">1</span><span lang="EN-US"><span>£</span></span><em><span lang="EN-US">U<sub>i</sub></span></em><span lang="EN-US">, <em>V<sub>i</sub></em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>N</em></span><span>，</span><span lang="EN-US">1 </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> <em>T<sub>i</sub></em> </span><span lang="EN-US"><span>£</span></span><span lang="EN-US"> 1000000000</span><span>），表示街道</span><em><span lang="EN-US">i</span></em><span>连接居住点</span><em><span lang="EN-US">U<sub>i</sub></span></em><span>和</span><em><span lang="EN-US">V<sub>i</sub></span></em><span>，并且经过街道</span><em><span lang="EN-US">i</span></em><span>需花费</span><em><span lang="EN-US">T<sub>i</sub></span></em><span>分钟。街道信息不会重复给出。</span></p>


<h2><span>【输出文件】</span></h2>

<p class="MsoNormalIndent"><span>输出文件</span><span lang="EN-US">hookey.out</span><span>仅包含整数</span><em><span lang="EN-US">T</span></em><span>，即最坏情况下</span><span lang="EN-US">Chris</span><span>的父母需要花费</span><span lang="EN-US">T</span><span>分钟才能找到</span><span lang="EN-US">Chris</span><span>。</span></p>


<h2><span>【样例输入】</span></h2>

<p class="a"><span lang="EN-US">4 3</span></p>
<p class="a"><span lang="EN-US">1 2 1</span></p>
<p class="a"><span lang="EN-US">2 3 1</span></p>
<p class="a"><span lang="EN-US">3 4 1</span></p>


<h2><span>【样例输出】</span></h2>

<p class="a"><span lang="EN-US">4</span></p>

上次修改时间 2017-05-26

《逃学的小孩》

相关日志