虚树+树形DP
本题100W的点数……不用虚树真的好吗……
Orz ZYF
我的感悟：
dp的过程跟SPOJ 1825 FTOUR2 的做法类似，依次枚举每个子树，从当前子树和之前的部分中各找一条最长（短）路径更新答案，再把这个子树的最短路径加入到x节点中去（之前算过的部分）这样就实现了枚举所有可能的最优情况！而且复杂度很低！避免了两两之间的枚举……
/**************************************************************
Problem: 3611
User: Tunix
Language: C++
Result: Accepted
Time:7460 ms
Memory:181024 kb
****************************************************************/ //BZOJ 3611
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')sign=-;ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*=sign;
}
/******************tamplate*********************/
const int N=,INF=~0u>>;
typedef long long LL; int n,m,dfn[N],dfs_clock,dep[N],fa[N][],a[N];
LL ans,g[N];
int f[N],_min[N],_max[N],ans1,ans2;
bool v[N]; inline int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
F(i,,) if(t&(<<i)) x=fa[x][i];
if (x==y) return x;
D(i,,) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][];
}
struct graph{
int head[N],to[N<<],next[N<<],len[N<<],cnt;
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;
}
void ad(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; len[cnt]=dep[y]-dep[x];
}
void dfs(int x){
dfn[x]=++dfs_clock;
F(i,,) if(dep[x]>=(<<i)) fa[x][i]=fa[fa[x][i-]][i-]; else break;
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x][]){
fa[to[i]][]=x;
dep[to[i]]=dep[x]+;
dfs(to[i]);
}
}
void DP(int x){
f[x]=v[x]; g[x]=;
_min[x]=v[x] ? : INF;
_max[x]=v[x] ? : -INF;
for(int i=head[x];i;i=next[i]){
int y=to[i];
DP(y);
ans+=(g[x]+f[x]*len[i])*f[y]+g[y]*f[x];
f[x]+=f[y];
g[x]+=g[y]+(LL)len[i]*f[y];
ans1=min(ans1,_min[x]+_min[y]+len[i]);
ans2=max(ans2,_max[x]+_max[y]+len[i]);
_min[x]=min(_min[x],_min[y]+len[i]);
_max[x]=max(_max[x],_max[y]+len[i]);
}
head[x]=;
}
}G1,G2;
inline bool cmp(int a,int b){ return dfn[a]<dfn[b]; }
int st[N],top;
int main(){
// freopen("3611.in","r",stdin);
n=getint();
int x,y;
F(i,,n){
x=getint(); y=getint();
G1.add(x,y);
}
G1.dfs(); int T=getint();
while(T--){
m=getint();
F(i,,m) {a[i]=getint(); v[a[i]]=;}
sort(a+,a+m+,cmp); st[top=]=; G2.cnt=;
ans=; ans1=INF; ans2=-INF;
F(i,,m){
int x=a[i],f=LCA(x,st[top]);
while(dep[f]<dep[st[top]]){
if(dep[f]>=dep[st[top-]]){
G2.ad(f,st[top--]);
if(st[top]!=f) st[++top]=f;
break;
}
G2.ad(st[top-],st[top]); top--;
}
if(st[top]!=x) st[++top]=x;
}
while(--top) G2.ad(st[top],st[top+]);
G2.DP();
printf("%lld %d %d\n",ans,ans1,ans2);
F(i,,m) v[a[i]]=;
}
return ;
}
3611: [Heoi2014]大工程
Time Limit: 60 Sec Memory Limit: 512 MB
Submit: 273 Solved: 129
[Submit][Status][Discuss]
Description
国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间 新建 C(k,2)条 新通道。
现在对于每个计划，我们想知道：
1.这些新通道的代价和
2.这些新通道中代价最小的是多少
3.这些新通道中代价最大的是多少
Input
第一行 n 表示点数。
接下来 n-1 行，每行两个数 a,b 表示 a 和 b 之间有一条边。
点从 1 开始标号。 接下来一行 q 表示计划数。
对每个计划有 2 行，第一行 k 表示这个计划选中了几个点。
第二行用空格隔开的 k 个互不相同的数表示选了哪 k 个点。
Output
输出 q 行，每行三个数分别表示代价和，最小代价，最大代价。
Sample Input
10
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1
2 1
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
2
5 4
2
10 4
2
5 2
2
6 1
2
6 1
Sample Output
3 3 3
6 6 6
1 1 1
2 2 2
2 2 2
6 6 6
1 1 1
2 2 2
2 2 2
HINT
n<=1000000
q<=50000并且保证所有k之和<=2*n