最近又一堆比赛，存下模板。以前题解都存在QQ空间， 现在QQ空间不支持搜日志了，转一些模板到这吧。
在线LCA，树上距离 http://hihocoder.com/contest/msbop2014r3/solution/139993
最优路径覆盖？忘了。费用流 http://hihocoder.com/contest/msbopqual/solution/55048
分块离线处理区间查询：http://hihocoder.com/contest/challenge10/solution/318976
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int INF = 1000000005;
const int MOD = 1000000007;
const int N = 100005;
//typedef __int64 ll;
typedef long long ll;
typedef pair<int,int> per;
#define mp(x,y) make_pair(x,y)
vector<per>E[N];
int w[N],b[N],fa[N],dep[N],ds[N];
bool cmp(int x,int y){return w[x]>w[y];}
void dfs(int x,int f,int de,int d)
{
fa[x]=f;
dep[x]=de;
ds[x]=d;
for(int i=E[x].size()-1;i>=0;i--)
{
int j=E[x][i].first;
if(j!=f)
{
dfs(j,x,de+1,d+E[x][i].second);
}
}
}
int ff[N][20];
int lca(int x,int y)
{
if(dep[x]>dep[y])x^=y^=x^=y;
int i;
for(i=19;i>=0;i--)
{
if(dep[y]-dep[x]>=(1<<i))
{
y=ff[y][i];
}
}
if(x==y)return x;
for(i=19;i>=0;i--)
{
if(ff[x][i]!=ff[y][i])
{
x=ff[x][i];
y=ff[y][i];
}
}
return fa[x];
}
int dis(int x,int y)
{
int w=lca(x,y);
return ds[x]+ds[y]-ds[w]-ds[w];
}
int main()
{
int n,i,h,T,ca=1;
scanf("%d",&T);
while(T--)
{
printf("Case %d: ",ca++);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&w[i]);
for(i=1;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
E[a].push_back(mp(b,c));
E[b].push_back(mp(a,c));
}
dfs(1,0,0,0);
for(i=1;i<=n;i++)ff[i][0]=fa[i];
for(h=1;h<20;h++)
{
for(i=1;i<=n;i++)
{
ff[i][h]=ff[ff[i][h-1]][h-1];
}
}
for(i=1;i<=n;i++)b[i]=i;
sort(b+1,b+n+1,cmp);
int ld=0,rd=0,len=0;
ll ret=0;
for(i=1;i<=n;i++)
{
int x=b[i];
if(i==1)
{
ld=x;
}
else if(i==2)
{
rd=x;
len=dis(ld,rd);
ret=(ll)w[x]*len;
}
else
{
int d1=dis(x,ld),d2=dis(x,rd);
int mx=d1>d2?d1:d2;
ll tmp=(ll)mx*w[x];
if(ret<tmp)ret=tmp;
if(d1>len)
{
rd=x;
len=d1;
}
else if(d2>len)
{
ld=x;
len=d2;
}
}
}
printf("%lld
",ret);
for(i=1;i<=n;i++)E[i].clear();
}
return 0;
}