Topcoder SRM 635 Div2 T3 LonglongestPathTree 题解

This blog post is only available in Simplified Chinse.

Topcoder Single Round Match 635 Div2 T3 LonglongestPathTree 题解

Translation

有一棵加权树，你可以从树中删除一条边，并添加一条长度相同的边，并且保证这样的操作过后新的图仍然是一棵树。计算并返回这样操作过后的树的最大直径。

树以三个 vector A, B 和 L 给出，表示 A[i] 和 B[i] 之间有一条长度为 L[i] 的边， $0 \leqslant i \leqslant n-2$ 。点从 0 开始编号。数据范围： $2 \leqslant n \leqslant 2000$ 。（为什么 TC 一遇到正经题目数据范围就这么大？！）

N will be between 2 and 2,000, inclusive.

Arrays A, B and L will each contain N-1 elements.

Each element of A and B will be between 0 and N-1, inclusive.

Each element of L will be between 1 and 1,000,000,000, inclusive.

A and B will describe a tree.

Time limit (s): 2.000

Memory limit (MB): 256

Stack limit (MB): 256

Examples

样例零：

{0,0,0}
{1,2,3}
{2,4,8}

Returns: 14

原来的树最远的点对是 (2,3)，他们之间的距离（即直径）是 12。如果我们移除边 1-0 并添加 3-1，则新的树直径为 14，这个方案是最优的。

The tree has 4 vertices and 3 edges: 1-0 (length 2), 2-0 (length 4) and 0-3 (length 8). Currently, the farthest pair of vertices is (2,3); their distance is 8+4=12. If we remove the edge 1-0 and add an edge 3-1, we'll get a tree with edges 2-0 (length 4), 0-3 (length 8) and 3-1 (length 2). Now, the fathest pair of vertices is (2,1); their distance is 8+4+2=14. Obviously, we can't do better than that (but this is not the only way to achieve distance 14).

样例一：

{0,1,2,3}
{1,2,3,4}
{1,2,3,4}

Returns: 10

不需要更改树，答案已经最优了。

One optimal solution is not changing the tree.

样例二：

{0,1,0,3,0,6,7,7,8,9,11}
{1,2,3,4,5,5,5,8,9,10,9}
{100,1000,100,1000,1,10,10,10,10,100,100}

Returns: 2410

Original

There is a weighted tree with N vertices. The vertices are numbered 0 through N-1. You're given a description of the tree in three vector s: A, B and L. For each 0 <= i <= N-2, there's an edge between vertices A[i] and B[i]; the length of this edge is L[i]. In a tree, each pair of vertices is connected by exactly one simple path. The distance between those vertices is the sum of lengths of edges on that simple path. The diameter of the tree is the maximum of all those pairwise distances. You're allowed to remove one of the edges and then add another edge. There are two constraints: the length of this edge must be the same as the length of the removed edge and the resulting graph must again be a tree. Compute and return the maximum diameter of the resulting tree that can be achieved this way.

Analysis

看到这题，一股亲切感扑面而来。没错，就是这题！CodeForces 294E Shaass the Great：极其变态的树形 DP 与思维题，当时折腾了我半天的这题！

那题同样是删除一条边、添一条同样长度的边、保证一棵树……唯一的不同是：那题让我们求“新的树中两两点之间距离之和最小值”，即 $\displaystyle \frac {\sum_{i=1,j=1}^{i=n,j=n,i \not = j} dist(i,j)} 2$ 最小值；而这题让我们求“新的树中两两点之间距离的最大值（即直径）的最大值”，即 $\displaystyle max(dist(i,j))$ 的最大值。回顾那题的做法：枚举边，连接分开的两棵树的重心。这启发我们思考：会不会这题的做法也和树的直径、重心的什么性质有关呢？

看数据范围： $2 \leqslant n \leqslant 2000$ ……看来必须采用 $\Theta (N^2)$ 的做法。首先肯定是要枚举删除的边。删除这条边以后原来的树分成了两棵树。接下来假设我们加入了这条边，称为 $add\\_ edge$ ，分类讨论：

如果新的直径没有经过这条边，那么等于新的直径不会大于两棵分开的树的直径……说明添加这条边没什么意义……所以既然我们添加了边，那么新的树的直径一定要经过这条边。
既然新的树直径通过 $add \\_ edge$ ，那么就是左边的树连到 $add\\_ edge$ 的左边端点，右边的树连到右边端点；我们可以思考：如何让左边的树、右边的树中，连到的 $add\\_ edge$ 的端点能走的最长路径最长呢？
“最长”的不就是直径吗？所以 $add\\_ edge$ 只需要连接左右两树的直径就可以了！！！

所以只要枚举 $add\\_ edge$ ，然后求左树直径、右树直径，加上这条边长度即可。

Code

Topcoder 的编译器又出锅了，极限数据本地跑是 0.18s，但是交上去超时……（上次似乎某题也是一样的情况）

#include <bits/stdc++.h>
#define CLEAR(_) memset(_,0,sizeof(_))
#define CLEAR_MAX(_) memset(_,0x3f,sizeof(_))
#define CLEAR_MIN(_) memset(_,0x80,sizeof(_))

using namespace std;
const int maxn=2005,maxe=4005;
int n;
int tot=0,lnk[maxn],nxt[maxe],son[maxe];
long long w[maxe];
long long ans;
bool vis[maxn];

class LonglongestPathTree {
public:
    long long getLength( vector <int> A, vector <int> B, vector <int> L ) ;
};

inline void add(int x,int y,int z){
	tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void init(){
	tot=0;CLEAR(lnk);CLEAR(nxt);CLEAR(son);CLEAR(w);
	ans=0;
}
inline long long Find(int x,int &res){
	vis[x]=true;res=x;
	long long now_ret=0;
	for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
		int nnd;
		long long nnf=Find(son[i],nnd)+w[i];
		if (nnf>now_ret) now_ret=nnf,res=nnd;
	}
	return now_ret;
}
long long LonglongestPathTree::getLength(vector <int> A, vector <int> B, vector <int> L) {
	init();
    n=A.size()+1;
	for (int i=0;i<n-1;i++) add(A[i],B[i],L[i]),add(B[i],A[i],L[i]);
	for (int i=0;i<n-1;i++){
		long long now=L[i],now1,now2;
		int x=-1,y=-1;

		CLEAR(vis);vis[B[i]]=true;
		x=y=-1;
		now1=Find(A[i],x);
		CLEAR(vis);vis[B[i]]=true;
		now2=Find(x,y);
		now+=max(now1,now2);

		CLEAR(vis);vis[A[i]]=true;
		x=y=-1;
		now1=Find(B[i],x);
		CLEAR(vis);vis[A[i]]=true;
		now2=Find(x,y);
		now+=max(now1,now2);

		ans=max(ans,now);
	}
	return ans;
}

9/1/2018