P2495

发表于 分类于
[SDOI2011]消耗战

[SDOI2011]消耗战

可以发现，对于每一个子问题，我们都可以 DP 解决。

但是每次都单独 DP 的消耗太大。

我们发现实际上关键的节点很少，我们的 DP 也主要是根据关键节点来的。

所以实际上我们可以尽量只保留关键的这些询问点，剩下的点能丢就丢。

这样我们就建成了一颗虚树。

问题是怎么建。

我个人觉得建虚树在树剖的基础上是比较好的，比如说这题，虚树边权什么的在树剖上查询是比较好的。。。

我也不知道是不是有什么其他奇技淫巧，我是在 ST 表上查的，感觉效率还可以吧。。。

正好树剖也给每个点一个 DFS 序的编号，直接用这个编号就完了。

考虑虚树的建树过程，使用单调栈：

  1. 向单调栈中加入 1 号节点（作为根节点）。

  2. 求出该点与栈顶的 LCA，然后就要分开讨论什么的：

    如果说这个 LCA 就是栈顶元素，说明目前栈内的点还在一条链上，初始化加入点的邻接表，压入栈内即可。

    如果说不是栈顶元素，那么说明加入点与目前的栈内元素不在一条链上。那就从栈顶开始弹出元素，一边弹出，一边和栈顶下的那个栈元素连边。一直弹出到栈顶元素的 DFS 序小于 LCA 的 DFS 序（这样的话栈顶元素在 LCA 上面，一条新的链出现了），或者弹出到栈顶元素就是 LCA（不用多解释了）。

    这个时候如果栈顶不是 LCA，我们先清空 LCA 的邻接表，连上我们刚才删掉的链的节点，然后压入 LCA；如果栈顶就是 LCA，直接连上边即可。

    最后记得把关键点压入即可。

  3. 最后在所有点都处理完之后，我们的单调栈里肯定还有元素，它们都是属于一条链上的，依次连上虚树边即可。

然后就是这题的细节问题，我们连上的虚树边只单纯知道两个端点，其权值应该是什么？

根据这个题意，我们不难得出这个权值应该取两点间路径的最小边权，这个东西我们使用树剖上的 ST 表查询完成。

因为是边权，所以每个点存其到父亲的边权值，最后查询的时候一般重链都是和点权一样的查询方法，最后两个点到一个重链的时候把靠上的点位移一下，实际上就是 $id(x)\rightarrow id(x)+1$，特判一下是不是合法区间，直接查就完了。

实际上就是月下毛景树。。。

时间复杂度 $O(\sum k _ i \log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=2e6,inf=(1ll<<31)-1;

ll n,k,tot,tc,cnt;
ll flg[N+5],h[N+5],st[N+5];
ll ver[N+5],nxt[N+5],head[N+5],wt[N+5];
ll vc[N+5],nc[N+5],hc[N+5],wc[N+5];
ll st_mi[N+5][30],lg[N+5];
ll fa[N+5],dt[N+5],top[N+5],siz[N+5],id[N+5],a[N+5],hs[N+5];

inline void ST_Pre() {
  for(ll i=1;i<=n;i++) {st_mi[i][0]=a[i];}
  for(ll i=1;i<=n;i++) lg[i]=lg[i-1]+((1<<lg[i-1])==i);
  for(ll j=1;j<=lg[n];j++) {
    for(ll i=1;i+(1<<j)-1<=n;i++) {
      st_mi[i][j]=min(st_mi[i][j-1],st_mi[i+(1<<(j-1))][j-1]);
    }
  }
}

inline ll Askstmi(ll l,ll r) {
  ll tmp=lg[r-l+1]-1;
  return min(st_mi[l][tmp],st_mi[r-(1<<tmp)+1][tmp]);
}

inline ll Askmi(ll x,ll y) {
  ll ans=inf;
  while(top[x]!=top[y]) {
    if(dt[top[x]]<dt[top[y]]) swap(x,y);
    ans=min(ans,Askstmi(id[top[x]],id[x]));
    x=fa[top[x]];
  }
  if(id[x]>id[y]) swap(x,y);
  if(id[x]+1<=id[y]) ans=min(ans,Askstmi(id[x]+1,id[y]));
  return ans;
}

inline void Addedge(ll u,ll v,ll w) {
  ver[++tot]=v;nxt[tot]=head[u];wt[tot]=w;head[u]=tot;
}

inline void Dfs(ll p,ll fath) {
  fa[p]=fath;dt[p]=dt[fath]+1;siz[p]=1;
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath) continue;
    Dfs(ver[i],p);siz[p]+=siz[ver[i]];
    if(siz[ver[i]]>siz[hs[p]]) hs[p]=ver[i];
  }
}

inline void Dfs_(ll p,ll fath,ll topf,ll tmpw) {
  id[p]=++cnt;a[cnt]=tmpw;top[p]=topf;
  if(!hs[p]) return;
  for(ll i=head[p];i;i=nxt[i]) {if(ver[i]==hs[p]) {tmpw=wt[i];break;}}
  Dfs_(hs[p],p,topf,tmpw);
  for(ll i=head[p];i;i=nxt[i]) {
    if(ver[i]==fath||ver[i]==hs[p]) continue;
    Dfs_(ver[i],p,ver[i],wt[i]);
  }
}

inline ll Getlca(ll x,ll y) {
  while(top[x]!=top[y]) {if(dt[top[x]]<dt[top[y]]) swap(x,y);x=fa[top[x]];}
  return dt[x]<dt[y]?x:y;
}

inline bool cmp(ll x,ll y) {return id[x]<id[y];}

inline void Addc(ll u,ll v) {
  vc[++tc]=v;nc[tc]=hc[u];wc[tc]=Askmi(u,v);hc[u]=tc;
}

inline void Build() {
  sort(h+1,h+k+1,cmp);
  ll top=1;
  st[top]=1;tc=0;hc[1]=0;
  for(ll i=1,lca;i<=k;i++) {
    if(h[i]!=1) {
      lca=Getlca(h[i],st[top]);
      if(lca!=st[top]) {
        while(id[lca]<id[st[top-1]]) {Addc(st[top-1],st[top]);top--;}
        if(id[lca]>id[st[top-1]]) {hc[lca]=0;Addc(lca,st[top]);st[top]=lca;}
        else {Addc(lca,st[top--]);}
      }
      hc[h[i]]=0;st[++top]=h[i];
    }
  }
  for(ll i=1;i<top;i++) Addc(st[i],st[i+1]);
}

inline ll DP(ll p,ll fath) {
  ll res=0;
  for(ll i=hc[p];i;i=nc[i]) {
    if(vc[i]==fath) continue;
    if(!flg[vc[i]]) res=res+min(DP(vc[i],p),wc[i]);
    else res=res+wc[i];
  }
  return res;
}

int main() {

  n=read();

  for(ll i=1;i<n;i++) {
    ll u,v,w;u=read();v=read();w=read();
    Addedge(u,v,w);Addedge(v,u,w);
  }

  Dfs(1,0);Dfs_(1,0,1,0);ST_Pre();

  ll m;m=read();

  while(m--) {
    k=read();
    for(ll i=1;i<=k;i++) {h[i]=read();flg[h[i]]=1;}
    Build();writeln(DP(1,0));
    for(ll i=1;i<=k;i++) flg[h[i]]=0;
  }

  return 0;
}