bzoj 3611

和BZOJ消耗站一样，先将那个询问的简图构建出来，然后就是简单的树形DP。

（倍增数组开小了，然后就狂WA，自己生成的极限数据深度又没有那么高，链又奇迹般正确）

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define oo 0x3f3f3f3f3f3f3f3f

 #define N 1000010

 #define P 19

 using namespace std;

 typedef long long dnt;

 int n, m;

 vector<int> g[N];

 int dfn[N], anc[N][P+], dep[N], idc;

 int head[N], ikey[N], dest[N+N], next[N+N], etot;

 dnt dp[N][];

 int qcnt, aa[N], stk[N], top;

 dnt ans[];

 void adde( int u, int v ) {

     etot++;

     next[etot] = head[u];

     dest[etot] = v;

     head[u] = etot;

 }

 void dfs( int u ) {

     dfn[u] = ++idc;

     for( int p=; p<=P; p++ )

         anc[u][p] = anc[anc[u][p-]][p-];

     for( int t=; t<g[u].size(); t++ ) {

         int v=g[u][t];

         if( v==anc[u][] ) continue;

         anc[v][] = u;

         dep[v] = dep[u]+;

         dfs(v);

     }

 }

 bool cmp( int u, int v ) {

     return dfn[u]<dfn[v];

 }

 int lca( int u, int v ) {

     if( dep[u]<dep[v] ) swap(u,v);

     int t=dep[u]-dep[v];

     for( int p=; t; t>>=,p++ )

         if( t& ) u=anc[u][p];

     if( u==v ) return u;

     for( int p=P; p>= && anc[u][]!=anc[v][]; p-- )

         if( anc[u][p]!=anc[v][p] ) u=anc[u][p], v=anc[v][p];

     return anc[u][];

 }

 void build() {

     stk[top=] = ;

     head[] = ;

     sort( aa+, aa++qcnt, cmp );

     etot = ;

     for( int i=-(aa[]!=); i<=qcnt; i++ ) {

         int ca=lca(aa[i],stk[top]);

         while( dep[ca]<dep[stk[top]] ) {

             int u;

             u = stk[top--];

             if( dep[ca]>=dep[stk[top]] ) {

                 if( ca!=stk[top] ) {

                     stk[++top] = ca;

                     head[ca] = ;

                 }

                 adde( stk[top], u );

                 break;

             }

             adde( stk[top], u );

         }

         stk[++top] = aa[i];

         head[aa[i]] = ;

     }

     for( int i=top; i>=; i-- )

         adde( stk[i-], stk[i] );

 }

 dnt sml, big, sum, cnt;

 void dodp( int u ) {

     if( ikey[u] ) {

         dp[u][] = ;

         dp[u][] = ;

         dp[u][] = ;

         dp[u][] = ;

     } else {

         dp[u][] = oo;

         dp[u][] = -oo;

         dp[u][] = ;

         dp[u][] = ;

     }

     for( int t=head[u]; t; t=next[t] ) {

         int v=dest[t];

         dnt w=dep[v]-dep[u];

         dodp(v);

         dp[u][] = min( dp[u][], dp[v][]+w );

         dp[u][] = max( dp[u][], dp[v][]+w );

         dp[u][] += dp[v][];

         dp[u][] += dp[v][]+w*dp[v][];

     }

     if( ikey[u] ) {

         sml = ;

         big = ;

         sum = ;

         cnt = ;

     } else {

         sml = oo;

         big = -oo;

         sum = ;

         cnt = ;

     }

     for( int t=head[u]; t; t=next[t] ) {

         int v=dest[t];

         dnt w=dep[v]-dep[u];

         ans[] = min( ans[], sml+w+dp[v][] );

         ans[] = max( ans[], big+w+dp[v][] );

         ans[] += cnt*(dp[v][]+w*dp[v][]) + sum*dp[v][];

         sml = min( sml, dp[v][]+w );

         big = max( big, dp[v][]+w );

         cnt += dp[v][];

         sum += dp[v][]+w*dp[v][];

     }

 }

 int main() {

     scanf( "%d", &n );

     for( int i=,u,v; i<n; i++ ) {

         scanf( "%d%d", &u, &v );

         g[u].push_back( v );

         g[v].push_back( u );

     }

     anc[][] = ;

     dep[] = ;

     dfs();

     scanf( "%d", &m );

     for( int i=; i<=m; i++ ) {

         scanf( "%d", &qcnt );

         for( int j=; j<=qcnt; j++ )

             scanf( "%d", aa+j );

         if( qcnt== ) {

             printf( "0 0 0\n" );

             continue;

         }

         build();

         for( int j=; j<=qcnt; j++ )

             ikey[aa[j]] = ;

         ans[] = oo;

         ans[] = ;

         ans[] = ;

         dodp();

         for( int j=; j<=qcnt; j++ )

             ikey[aa[j]] = ;

         printf( "%lld %lld %lld\n", ans[], ans[], ans[] );

     }

 }