solution-code3329

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define LL long long
6
using namespace std;
7
struct Node
8
{
9
  int to,next;
10
  LL val;
11
}e[500005];
12
int n,a[250005],h[250005],low[250005],d[250005],f[250005][19],st[250005],flag[250005],cnt,sign,qid;
13
LL dp[250005],maxv[250005];
14
inline void Addedge(int x,int y,LL v)
15
{
16
  e[++cnt]=(Node){y,h[x],v};h[x]=cnt;
17
  e[++cnt]=(Node){x,h[y],v};h[y]=cnt;
18
  return;
19
}
20
inline bool cmp(const int& x,const int& y)
21
{
22
  return low[x]<low[y];
23
}
24
inline void dfs(int x,int pre,LL val)
25
{
26
  int i,y;
27
  low[x]=++sign;
28
  d[x]=d[pre]+1;
29
  f[x][0]=pre;
30
  maxv[x]=min(maxv[pre],val);
31
  for(i=h[x];i;i=e[i].next)
32
  {
33
    y=e[i].to;
34
    if(y==pre)continue;
35
    dfs(y,x,e[i].val);
36
  }
37
  return;
38
}
39
inline void Init()
40
{
41
  int i,j;
42
  for(j=1;j<=18;++j)
43
  {
44
    for(i=1;i<=n;++i)f[i][j]=f[f[i][j-1]][j-1];
45
  }
46
  return;
47
}
48
inline int LCA(int x,int y)
49
{
50
  int i;
51
  if(d[x]<d[y])swap(x,y);
52
  for(i=18;i>=0;--i)
53
  {
54
    if(d[f[x][i]]>=d[y])x=f[x][i];
55
  }
56
  if(x==y)return x;
57
  for(i=18;i>=0;--i)
58
  {
59
    if(f[x][i]==f[y][i])continue;
60
    x=f[x][i];y=f[y][i];
61
  }
62
  return f[x][0];
63
}
64
inline LL DP(int x,int pre)
65
{
66
  int i,y;
67
  if(flag[x]==qid)return maxv[x];
68
  for(i=h[x];i;i=e[i].next)
69
  {
70
    y=e[i].to;
71
    if(y==pre)continue;
72
    dp[x]+=DP(y,x);
73
  }
74
  return dp[x]=min(dp[x],1LL*maxv[x]);
75
}
76
inline void Printst()
77
{
78
  for(int i=1;i<=st[0];++i)printf("%d ",st[i]);
79
  return;
80
}
81
inline int Build(int m)
82
{
83
  int i,x,y,lca,tmp=m;
84
  for(i=1;i<=m;++i)flag[a[i]]=qid;
85
  sort(a+1,a+m+1,cmp);a[++m]=1;
86
  for(i=1;i<tmp;++i)a[++m]=LCA(a[i],a[i+1]);
87
  sort(a+1,a+m+1,cmp);
88
  tmp=m;m=1;
89
  for(i=2;i<=tmp;++i)
90
  {
91
    if(a[i]==a[i-1])continue;
92
    a[++m]=a[i];
93
  }
94
  st[st[0]=1]=a[1];
95
  for(i=1;i<=m;++i)h[a[i]]=dp[a[i]]=0;
96
  cnt=0;
97
  for(i=2;i<=m;++i)
98
  {
99
    x=a[i];y=st[st[0]];
100
    lca=LCA(x,y);
101
    while(st[st[0]]!=lca)
102
    {
103
      Addedge(st[st[0]],st[st[0]-1],0);
104
      --st[0];
105
    }
106
    st[++st[0]]=x;
107
  }
108
  while(st[st[0]]!=1)
109
  {
110
    Addedge(st[st[0]],st[st[0]-1],0);
111
    --st[0];
112
  }
113
  return m;
114
}
115
inline void Solve(int m)
116
{
117
  m=Build(m);
118
  printf("%lld\n",DP(1,0));
119
  return;
120
}
121
int main(void)
122
{
123
  int m,T,i,j,x,y;
124
  LL v;
125
  scanf("%d",&n);
126
  for(i=1;i<n;++i)
127
  {
128
    scanf("%d%d%lld",&x,&y,&v);
129
    Addedge(x,y,v);
130
  }
131
  maxv[0]=1LL<<60;
132
  dfs(1,0,1LL<<60);
133
  Init();
134
  scanf("%d",&T);
135
  for(i=1;i<=T;++i)
136
  {
137
    qid=i;
138
    scanf("%d",&m);
139
    for(j=1;j<=m;++j)scanf("%d",&a[j]);
140
    Solve(m);
141
  }
142
  return 0;
143
}