題目連結
作為一個電子商務為主體的公司，京東一直努力實作自己“多、快、好、省”的承諾。其中，“快”的特質更是被京東發揮到了極緻。京東建立了一個非常高效的物流網絡，物流網絡構成了一個樹結構，由很多的物流點和将物流點連結起來的道路組成。
京東物流網絡中每個物流點有一個權值 di，物流點間的道路也都有一個權值 wi。對于一條物流網絡中的路徑，令路徑上所有物流點權值 di 的最小值為 mind，路徑上所有道路權值 wi 的總和為 sumw，則該條路徑的總權值為 mind* sumw。路徑的起點和終點可以是物流網絡中的任意物流點，且路徑中不能出現重複的物流點。
請求出京東的這個樹形物流網絡所有路徑總權值中的最大值。
輸入格式
第一行輸入一個整數 T（1 ≤ T ≤ 50），表示資料組數。
每組資料第一行一個整數 n（1 ≤ n ≤ 105），表示有 n 個物流點。
之後一行 n 個整數，表示每個物流點的權重 di（1 ≤ di ≤ 109）。
接下來有 n - 1 行，每行 3 個整數 ui，vi，wi（1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109），表示有一條連接配接 ui 和 vi 的權值為 wi的道路。輸入資料保證沒有重複出現的（ui，vi）點對，且最終一定會形成一個樹形物流網絡。
最多有 10 組資料的 n 超過 104。
輸出格式
一共輸出 T 行，每行一個整數，表示路徑總權值的最大值。
樣例1
輸入：
1
3
1 2 3
1 2 1
1 3 2 輸出：
3 提示資訊
總權值最大的路徑是 2 - 1 - 3，mind 為 min(1, 2, 3) = 1，sumw 為 sum(1, 2) = 3，是以總權值為 1 * 3 = 3。
思路：樹分治。求得重心，以重心為樹根周遊所在子樹，求得所有點到根的路徑資訊（子樹編号、路徑長度、路徑最小點權）。
關鍵在于如何高效率的更新答案，思路為先按照路徑最小點權由小到大排序，從後往前周遊，對于目前路徑，滿足要求的解為，樹編号不一樣的且不小于其最小點權的路徑長度最大的。是以要記錄并更新之前的最長路徑，和與最長路徑子樹編号不一樣的次長路徑，這樣最優答案即為其中與目前路徑編号不一樣的一個。
當時比賽時不知道樹分治的思想，普通思路一直逾時。題解說點分治，并不知道什麼意思，這幾天學習了樹分治想起這個題，便根據自己的了解敲了一遍。
#pragma comment(linker, "/STACK:10240000000,10240000000")
#include<iostream>
#include<stdio.h>
#include<math.h>
#include <string>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include<utility>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mo(x) memset(x,0,sizeof(x))
#define ll long long int
#define mod 1000000007
#define maxn 101000
#define maxm 10000001
int mi(int a,int b){return a<b?a:b;}
int ma(int a,int b){return a>b?a:b;}
struct node
{
int v,w,next;
}edge[maxn*2];
int head[maxn],vis[maxn],tot;
int d[maxn],sz[maxn],mx[maxn];
//ll dis[maxn];
ll res;
int n,nn;
void init(){
tot=0;
memset(head,-1,sizeof head);
mo(vis);
}
void addedge(int u,int v,int w){
edge[tot].v=v;edge[tot].w=w;edge[tot].next=head[u];
head[u]=tot++;
}
void dfsize(int x,int fa){//統計子樹大小
sz[x]=1;mx[x]=0;
for(int i=head[x];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa||vis[v]) continue;
dfsize(v,x);
sz[x]+=sz[v];
if(sz[v]>mx[x]) mx[x]=sz[v];
}
}
void dfsroot(int r,int x,int fa,int &root,int &mm){//求重心
if(sz[r]-sz[x]>mx[x]) mx[x]=sz[r]-sz[x];
if(mx[x]<mm) mm=mx[x],root=x;
for(int i=head[x];i!=-1;i=edge[i].next){
int v=edge[i].v;
if(v==fa||vis[v]) continue;
dfsroot(r,v,x,root,mm);
}
}
struct dd//儲存到中心的路徑的sumw、k（分支編号）、md（最小點權）
{
ll w;
int md,k;
dd(){}
dd(int kk,int mmd,ll ww){w=ww;md=mmd;k=kk;}
}dis[maxn];
bool cmp(dd a,dd b){
return a.md<b.md;
}
void dfsdis(int r,int x,int fa,int k,ll ww,int md){//求得從中心出發的所有路徑
dis[nn++]=dd(k,md,ww);
for(int i=head[x];i!=-1;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(v==fa||vis[v]) continue;
dfsdis(r,v,x,k,ww+w,mi(md,d[v]));
}
}
void cal(int r){
nn=0;
int k=1;
for(int i=head[r];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
int w=edge[i].w;
if(vis[v]) continue;
//dis[nn]=0;
dfsdis(r,v,r,k,w,mi(d[v],d[r]));
k++;
}
sort(dis,dis+nn,cmp);
dd m1=dd(0,0,0);
dd m2=dd(0,0,0);
for(int i=nn-1;i>=0;i--){//周遊路徑更新答案
ll ww=m1.k==dis[i].k?m2.w:m1.w;
ll res1=(ww+dis[i].w)*dis[i].md;
res=res<res1?res1:res;
if(dis[i].w>=m1.w){
if(dis[i].k==m1.k) m1=dis[i];
else {
m2=m1;m1=dis[i];
}
}
else if(dis[i].w>m2.w&&dis[i].k!=m1.k) m2=dis[i];
}
}
void solve(int x){
dfsize(x,x);
int mm=n+1;
int root;
dfsroot(x,x,x,root,mm);//求重心
cal(root);//計算過重心的最優答案
vis[root]=1;
for(int i=head[x];i!=-1;i=edge[i].next){//分治
int v=edge[i].v;
if(vis[v]) continue;
solve(v);
}
}
int main()
{
int t,u,v,w;
rd(t);
while(t--){
rd(n);
init();
for(int i=1;i<=n;i++) rd(d[i]);
for(int i=1;i<n;i++){
rd3(u,v,w);
addedge(u,v,w);
addedge(v,u,w);
}
res=0;
solve(1);
printf("%lld\n",res);
}
return 0;
}
![【JZOJ5055】【GDOI2017模拟二試4.12】樹上路徑[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)