问题分析
首先不难想到是虚树。建完虚树需要保持节点间原先的距离关系。
然后总距离和最小距离用树形DP求，最大距离用两遍dfs即可。注意统计的时候只对关键点进行统计。
真是麻烦
参考程序
ac的时候是loj上速度最后一页，代码第四长的……
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1000010;
const long long INF = 1000000000010;
const int MaxLog = 20;
struct edge {
int To, Next;
long long Length;
edge() : To( 0 ), Next( 0 ), Length( 0LL ) {}
edge( int _To, int _Next, long long _Length ) :
To( _To ), Next( _Next ), Length( _Length ) {}
};
int n, q, k, A[ Maxn ], Important[ Maxn ];
int DFa[ Maxn ][ MaxLog ], Deep[ Maxn ], Dfn[ Maxn ], Time;
int Stack[ Maxn ];
int Flag[ Maxn ];
struct graph {
int Start[ Maxn ], Used, State;
edge Edge[ Maxn << 1 ];
graph() {}
inline void Init( int _DYT ) {
State = _DYT;
Used = 0;
return;
}
inline void AddDirectedEdge( int x, int y, long long Len ) {
if( Flag[ x ] != State ) {
Flag[ x ] = State;
Start[ x ] = 0;
}
Edge[ ++Used ] = edge( y, Start[ x ], Len );
Start[ x ] = Used;
return;
}
inline void AddUndirectedEdge( int x, int y, long long Len ) {
AddDirectedEdge( x, y, Len );
AddDirectedEdge( y, x, Len );
return;
}
};
graph Prime, Now;
long long Ans, Max, Min;
int Size[ Maxn ], Id;
void Build( int u, int Fa ) {
Deep[ u ] = Deep[ Fa ] + 1;
Dfn[ u ] = ++Time;
DFa[ u ][ 0 ] = Fa;
for( int i = 1; i < MaxLog; ++i )
DFa[ u ][ i ] = DFa[ DFa[ u ][ i - 1 ] ][ i - 1 ];
for( int t = Prime.Start[ u ]; t; t = Prime.Edge[ t ].Next ) {
int v = Prime.Edge[ t ].To;
if( v == Fa ) continue;
Build( v, u );
}
return;
}
inline bool Cmp( int x, int y ) {
return Dfn[ x ] < Dfn[ y ];
}
int GetLca( int x, int y ) {
if( Deep[ x ] < Deep[ y ] ) swap( x, y );
for( int i = MaxLog - 1; i >= 0; --i )
if( Deep[ DFa[ x ][ i ] ] >= Deep[ y ] )
x = DFa[ x ][ i ];
if( x == y ) return x;
for( int i = MaxLog - 1; i >= 0; --i )
if( DFa[ x ][ i ] != DFa[ y ][ i ] ) {
x = DFa[ x ][ i ];
y = DFa[ y ][ i ];
}
return DFa[ x ][ 0 ];
}
struct info {
long long Min, Sec;
info() : Min( INF ), Sec( INF ) {}
info( long long _Min, long long _Sec ) : Min( _Min ), Sec( _Sec ) {}
inline info operator + ( const long long Other ) const {
return info( Min + Other, Sec + Other );
}
inline info operator + ( const info Other ) const {
return ( Min < Other.Min ) ? info( Min, min( Sec, Other.Min ) ) : info( Other.Min, min( Min, Other.Sec ) ) ;
}
};
info GetMin( int u, int Fa ) {
info Ans = info( INF, INF );
if( Important[ u ] == Now.State ) Ans.Min = 0;
for( int t = Now.Start[ u ]; t; t = Now.Edge[ t ].Next ) {
int v = Now.Edge[ t ].To;
if( v == Fa ) continue;
Ans = Ans + ( GetMin( v, u ) + Now.Edge[ t ].Length );
}
Min = min( Min, Ans.Min + Ans.Sec );
return Ans;
}
void GetMax( int u, int Fa, long long Len ) {
if( Len > Max && Important[ u ] == Now.State ) {
Max = Len;
Id = u;
}
for( int t = Now.Start[ u ]; t; t = Now.Edge[ t ].Next ) {
int v = Now.Edge[ t ].To;
if( v == Fa ) continue;
GetMax( v, u, Len + Now.Edge[ t ].Length );
}
return;
}
long long GetAns( int u, int Fa ) {
Size[ u ] = 0; long long Sum = 0;
if( Important[ u ] == Now.State ) Size[ u ] = 1;
for( int t = Now.Start[ u ]; t; t = Now.Edge[ t ].Next ) {
int v = Now.Edge[ t ].To;
if( v == Fa ) continue;
long long SS = GetAns( v, u );
Ans += Sum * Size[ v ] + Size[ u ] * ( Now.Edge[ t ].Length * Size[ v ] + SS );
Sum += SS + Now.Edge[ t ].Length * Size[ v ];
Size[ u ] += Size[ v ];
}
return Sum;
}
void Work( int Case ) {
Now.Init( Case );
scanf( "%d", &k );
for( int i = 1; i <= k; ++i ) scanf( "%d", &A[ i ] );
for( int i = 1; i <= k; ++i ) Important[ A[ i ] ] = Case;
sort( A + 1, A + k + 1, Cmp );
Stack[ 0 ] = 1; Stack[ 1 ] = 1;
int Len, Lca;
for( int i = 1; i <= k; ++i ) {
if( i == 1 && A[ 1 ] == 1 ) continue;
if( i > 1 && A[ i ] == A[ i - 1 ] ) continue;
Lca = GetLca( Stack[ Stack[ 0 ] ], A[ i ] );
if( Deep[ Lca ] == Deep[ Stack[ Stack[ 0 ] ] ] )
Stack[ ++Stack[ 0 ] ] = A[ i ];
else {
while( Deep[ Stack[ Stack[ 0 ] - 1 ] ] > Deep[ Lca ] ) {
Len = Deep[ Stack[ Stack[ 0 ] ] ] - Deep[ Stack[ Stack[ 0 ] - 1 ] ];
Now.AddUndirectedEdge( Stack[ Stack[ 0 ] - 1 ], Stack[ Stack[ 0 ] ], Len );
--Stack[ 0 ];
}
if( Deep[ Stack[ Stack[ 0 ] - 1 ] ] == Deep[ Lca ] ) {
Len = Deep[ Stack[ Stack[ 0 ] ] ] - Deep[ Stack[ Stack[ 0 ] - 1 ] ];
Now.AddUndirectedEdge( Stack[ Stack[ 0 ] - 1 ], Stack[ Stack[ 0 ] ], Len );
--Stack[ 0 ];
Stack[ ++Stack[ 0 ] ] = A[ i ];
} else {
Len = Deep[ Stack[ Stack[ 0 ] ] ] - Deep[ Lca ];
Now.AddUndirectedEdge( Stack[ Stack[ 0 ] ], Lca, Len );
--Stack[ 0 ];
Stack[ ++Stack[ 0 ] ] = Lca;
Stack[ ++Stack[ 0 ] ] = A[ i ];
}
}
}
while( Stack[ 0 ] > 1 ) {
Len = Deep[ Stack[ Stack[ 0 ] ] ] - Deep[ Stack[ Stack[ 0 ] - 1 ] ];
Now.AddUndirectedEdge( Stack[ Stack[ 0 ] ], Stack[ Stack[ 0 ] - 1 ], Len );
--Stack[ 0 ];
}
Min = INF;
GetMin( 1, 0 );
Max = -1;
GetMax( A[ 1 ], 0, 0 );
Max = -1;
GetMax( Id, 0, 0 );
Ans = 0;
GetAns( 1, 0 );
printf( "%lld %lld %lld\n", Ans, Min, Max );
return;
}
int main() {
scanf( "%d", &n );
for( int i = 1; i < n; ++i ) {
int x, y;
scanf( "%d%d", &x, &y );
Prime.AddUndirectedEdge( x, y, 1 );
}
Build( 1, 0 );
scanf( "%d", &q );
for( int i = 1; i <= q; ++i ) Work( i );
return 0;
}