- 题目思路：链式前向星存图，跑一遍LCA的预处理，判断一下深度为二的有几个点，和军队的总数比较一下来判断能否控制。然后二分答案，check函数先把每个军队往上提，看能否到根节点，如果不能，则把最近能到达的点标记一下，如果能到根节点，那就记一下记录根节点最近能到的一个点并记录，然后在把能到的点按边权排个序，把不能到的点按边权排个序，判断一下最优解是否能超过不能到达的点。
- 代码
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
using namespace std;
int sc() {
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
struct TREE {
int next,to,dis;
}edge[Maxn*2];
struct node {
int id;
long long v;
bool operator < (const node &x) const {
return v<x.v;
}
}a[Maxn*2],b[Maxn*2];
int n,cnt,m,ans,lena,lenb,all;
int head[Maxn*2],deep[Maxn],Fa[Maxn],army[Maxn];
int f[Maxn][22],Dis[Maxn][22];
bool vis[Maxn];
namespace DY {
void ADD(int from,int to,int dis) {
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
void D_F(int son,int fa) {
deep[son]=deep[fa]+1;
Fa[son]=fa;
for(int i=1; i<=20&& f[f[son][i-1]][i-1]; i++) {
f[son][i]=f[f[son][i-1]][i-1];
Dis[son][i]=Dis[f[son][i-1]][i-1]+Dis[son][i-1];
}
for(int i=head[son]; i; i=edge[i].next) {
int to=edge[i].to;
if(to==fa) continue;
f[to][0]=son;
Dis[to][0]=edge[i].dis;
D_F(to,son);
}
}
void ctrl(int now) {
int flag1=1,flag2=0;
for(int i=head[now]; i; i=edge[i].next) {
int to=edge[i].to;
if(to==Fa[now]) continue;
ctrl(to);
flag1&=vis[to];
flag2=1;
}
if(now!=-1&& flag1&& flag2) vis[now]=1;
}
bool chekc(int now) {
lena=lenb=0;
memset(vis,0,sizeof(vis));
for(int i=1; i<=m; i++) {
int x=army[i],num=0;
for(int j=20; j>=0; j--)
if(f[x][j]&& num+Dis[x][j]<=now)
num+=Dis[x][j],x=f[x][j];
if(x!=1) vis[x]=1;
else {
x=army[i];
a[++lena].v=now-num;
for(int j=20; j>=0; j--)
if(f[x][j]>1) x=f[x][j];
a[lena].id=x;
}
}
ctrl(1);
for(int i=head[1]; i; i=edge[i].next) {
int to=edge[i].to;
if(vis[to]) continue;
b[++lenb].id=to;
b[lenb].v=edge[i].dis;
}
sort(a+1,a+1+lena); sort(b+1,b+1+lenb);
int j=1;
for(int i=1; i<=lena; i++) {
if(!vis[a[i].id])
vis[a[i].id]=1;
else if(a[i].v>=b[j].v)
vis[b[j].id]=1;
while(vis[b[j].id]&& j<=lenb)
j++;
}
return j>lenb;
}
void main() {
n=sc();
int l=0,r=0;
for(int i=1; i<n; i++) {
int u=sc(),v=sc(),w=sc();
ADD(u,v,w); ADD(v,u,w);
r+=w;
}
all=r;
D_F(1,0);
m=sc();
for(int i=1; i<=m; i++)
army[i]=sc();
int num=0;
for(int i=1; i<=n; i++)
if(deep[i]==2) num++;
if(m<num) {
printf("-1");
return ;
}
while(l<=r) {
int mid=l+r>>1;
// cout<<l<<" "<<r<<endl<<endl;
if(chekc(mid)) {
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d",ans);
}
};
int main() {
DY::main();
return 0;
}