# Topcoder SRM 635 Div2 T3 LonglongestPathTree 题解

Topcoder Single Round Match 635 Div2 T3 LonglongestPathTree 题解

## Translation

（为什么 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

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

• 如果新的直径没有经过这条边，那么等于新的直径不会大于两棵分开的树的直径……说明添加这条边没什么意义……所以既然我们添加了边，那么新的树的直径一定要经过这条边。

• 既然新的树直径通过 $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++){
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;
}

# Related posts

Topcoder SRM 634 Div2 T3 SpecialStrings 题解