1 #include<algorithm> 2 #include<fstream> 3 #include<functional> 4 #include<iostream> 5 using namespace std; 6 static const int N=50001; 7 typedef long long int64; 8 struct node 9 { 10 int v,w; 11 node *next; 12 }alist[3*N]; 13 struct heapnode 14 { 15 int64 w; 16 int u; 17 bool operator>(const heapnode &r)const 18 { 19 return w>r.w; 20 } 21 }; 22 int p[N][19]; 23 int64 w[N][19]; 24 void dfs1(int u) 25 { 26 for(node *i=alist[u].next;i;i=i->next) 27 if(i->v!=p[u][0]) 28 { 29 p[i->v][0]=u; 30 w[i->v][0]=i->w; 31 dfs1(i->v); 32 } 33 } 34 bool visit[N]; 35 void dfs2(int u) 36 { 37 if(visit[u])return; 38 if(!alist[u].next->next)return; 39 visit[u]=true; 40 for(node *i=alist[u].next;i;i=i->next) 41 if(i->v!=p[u][0]) 42 { 43 dfs2(i->v); 44 if(!visit[i->v]) 45 { 46 visit[u]=false; 47 break; 48 } 49 } 50 } 51 int main() 52 { 53 ifstream fin("blockade.in"); 54 ofstream fout("blockade.out"); 55 int n(0),m(0); 56 fin>>n; 57 node *anode(alist+n+1); 58 for(int i=0;i<n-1;i++) 59 { 60 int u(0),v(0),ww(0); 61 fin>>u>>v>>ww; 62 anode->v=v; 63 anode->w=ww; 64 anode->next=alist[u].next; 65 alist[u].next=anode++; 66 anode->v=u; 67 anode->w=ww; 68 anode->next=alist[v].next; 69 alist[v].next=anode++; 70 } 71 fin>>m; 72 static int d[N]; 73 for(int i=0;i<m;i++) 74 fin>>d[i]; 75 int NScount=0; 76 for(node *i=alist[1].next;i;i=i->next) 77 { 78 NScount++; 79 p[i->v][0]=1; 80 w[i->v][0]=i->w; 81 dfs1(i->v); 82 } 83 if(NScount>m) 84 { 85 fout<<"-1"<<endl; 86 return 0; 87 } 88 for(int j=1;j<=18;j++) 89 for(int i=1;i<=n;i++) 90 { 91 p[i][j]=p[p[i][j-1]][j-1]; 92 w[i][j]=w[i][j-1]+w[p[i][j-1]][j-1]; 93 } 94 static heapnode a[N],b[N]; 95 heapnode *atop(0),*aback(0),*btop(0),*bback(0); 96 static int _w[N]; 97 for(node *i=alist[1].next;i;i=i->next) 98 _w[i->v]=i->w; 99 int64 l(0),r(1e16),ans(1e16); 100 greater<heapnode> comp; 101 while(l<=r) 102 { 103 atop=a; 104 aback=a; 105 btop=b; 106 bback=b; 107 int64 mm=(l+r)>>1; 108 for(int i=1;i<=n;i++) 109 visit[i]=false; 110 for(int i=0;i<m;i++) 111 { 112 int u=d[i]; 113 int64 ww=mm; 114 for(int j=18;j>=0;j--) 115 if(p[u][j]&&p[u][j]!=1&&ww>=w[u][j]) 116 { 117 ww-=w[u][j]; 118 u=p[u][j]; 119 } 120 if(/*p[u][0]==1&&*/ww>w[u][0]) 121 { 122 aback->w=ww-w[u][0]; 123 aback->u=u; 124 aback++; 125 push_heap(atop,aback,comp); 126 } 127 else visit[u]=true; 128 } 129 dfs2(1); 130 if(visit[1]) 131 { 132 ans=mm; 133 r=mm-1; 134 } 135 else 136 { 137 for(node *i=alist[1].next;i;i=i->next) 138 if(!visit[i->v]) 139 { 140 bback->w=i->w; 141 bback->u=i->v; 142 bback++; 143 push_heap(btop,bback,comp); 144 } 145 while(btop!=bback||atop!=aback) 146 { 147 while(atop!=aback&&!visit[atop->u]&&atop->w<_w[atop->u]) 148 { 149 visit[atop->u]=true; 150 pop_heap(atop,aback,comp); 151 aback--; 152 } 153 while(btop!=bback&&visit[btop->u]) 154 { 155 pop_heap(btop,bback,comp); 156 bback--; 157 } 158 if(btop==bback||atop==aback)break; 159 if(atop->w>=btop->w) 160 { 161 visit[btop->u]=true; 162 pop_heap(atop,aback,comp); 163 aback--; 164 pop_heap(btop,bback,comp); 165 bback--; 166 } 167 else 168 { 169 pop_heap(atop,aback,comp); 170 aback--; 171 } 172 } 173 if(btop==bback) 174 { 175 ans=min(ans,mm); 176 r=mm-1; 177 } 178 else l=mm+1; 179 } 180 } 181 fout<<ans<<endl; 182 return 0; 183 }