NOIP2012 疫情控制 题解（LuoguP1084）
不难发现，如果一个点向上移动一定能控制更多的点，所以可以二分时间，判断是否可行。
但根节点不能不能控制，存在以当前时间可以走到根节点的点，可使向下走到深度为2的节点控制 其他点，此时又可以进行另一个贪心，优先选择走到根节点还能再走的时间小的去控制深度一到二之间边权较小的。
某大佬有更加详尽的讲解，参见这里 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
143
144
145
146
147
148
149
150
151
152
using namespace std;
typedef long long ll;
const int MAXN=50000+5;
int anc[21][MAXN];
ll tab[21][MAXN];
struct Edge
{
int t,v,n;
}e[MAXN<<1];
int cnt,n,m,scnt;
int rsn[MAXN],siz[MAXN],army[MAXN],hd[MAXN],frm[MAXN];
bool cvef[MAXN],cover[MAXN];
typedef pair<int,int> pii;
pii a[MAXN],c[MAXN];
inline void build(int f,int t,int v)
{
e[++cnt]=(Edge){t,v,hd[f]};
hd[f]=cnt;
}
void dfs1(int u)
{
if(anc[0][u]==1)
frm[u]=u;
else frm[u]=frm[anc[0][u]];
for(int i=hd[u];i;i=e[i].n)
{
int v=e[i].t;
if(v==anc[0][u])
continue;
++siz[u];
anc[0][v]=u;
tab[0][v]=e[i].v;
for(int i=1;anc[i-1][v];++i)
{
anc[i][v]=anc[i-1][anc[i-1][v]];
tab[i][v]=tab[i-1][v]+tab[i-1][anc[i-1][v]];
}
dfs1(v);
}
}
void dfs2(int u)
{
cvef[u]=1;
if(siz[u]>1)
return;
for(int i=hd[u];i;i=e[i].n)
if(e[i].t!=anc[0][u])
dfs2(e[i].t);
}
void initrt()
{
for(int i=hd[1];i;i=e[i].n)
{
int v=e[i].t;
rsn[++scnt]=v;
dfs2(v);
}
}
bool check(ll mid)
{
memset(cover,0,sizeof cover);
int cntc=0,cnta=0;
for(int i=1;i<=m;++i)
{
ll tmp=mid;
int pos=army[i];
for(int j=20;j>=0;--j)
{
if(anc[j][pos]&&tmp>=tab[j][pos])
{
tmp-=tab[j][pos];
pos=anc[j][pos];
}
}
if(pos!=1)
{
if(cvef[pos])
cover[frm[pos]]=1;
}
else
a[++cnta]=pii(tmp,frm[army[i]]);
}
for(int i=1;i<=scnt;++i)
{
if(!cover[rsn[i]])
c[++cntc]=pii(tab[0][rsn[i]],rsn[i]);
}
if(cntc>cnta)
return 0;
sort(a+1,a+cnta+1);
sort(c+1,c+cntc+1);
int j=1;
int t=cntc;
for(int i=1;i<=cnta;++i)
{
if(!cover[a[i].second])
cover[a[i].second]=1,--t;
else
{
while(j<=cntc&&cover[c[j].second])
++j;
if(a[i].first>=c[j].first)
cover[c[j].second]=1,++j,--t;
}
}
if(t>0)
return 0;
return 1;
}
int main()
{
scanf("%d",&n);
int x,y,z;
ll l=0,r=0;
for(int i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
build(x,y,z);
build(y,x,z);
r+=z;
}
scanf("%d",&m);
for(int i=1;i<=m;++i)
scanf("%d",&army[i]);
dfs1(1);
initrt();
if(m<scnt)
{
puts("-1");
return 0;
}
while(r-l>1)
{
ll mid=l+r>>1;
if(check(mid))
r=mid;
else
l=mid;
}
printf("%lld",r);
return 0;
}看来是只是贪心二分等基础算法我也不会QAQ