[SCOI2008]城堡
最大值最小，显然二分答案，但考虑二分后如何 check。
\(n\) 个点 \(n\) 条边，显然这是一个基环树森林。对于基环树，常用的套路是拆环为链，枚举删去哪条边。但这题是基环树森林，拆环为链的复杂太高，考虑将环和树分开处理。
树上是一个很典型的 dp，和将军令一样（不了解的可以观看我的相关博客），注意处理下原来关键点的影响即可。
环上的部分要分成两种情况：
- 第一种是环上没有关键点。需要先处理该点是否被其它点子树内的关键点覆盖。令 \(len\) 表示处理完子树内的点后还可以影响环上多少长度，若 \(len\times 2>\) 环的长度，则整个环只需要新添一个点就可以全部被覆盖。否则会变成一个经典贪心问题，在环上有一些区间，每个区间表示表示关键点被放置在该区间时，某个点才会被覆盖，求最少要有多少区间才能覆盖这个环。
- 环上有关键点，其实也差不多，只是最后求最少区间覆盖环时有了一个起点。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=200,inf=1e9;
int n,m,K,d[N][N],v[N],w[N],flag[N],vis[N],f[N],g[N];
int idx,Time;
vector<pii>e[N];
stack<int>stk;
struct node{
int l,r;
};
struct tree{
int circle[N],cnt,rank[N],pos,dis[N],s[N],in_cir[N],sum,k,tot,R[N],nxt[N];
node seg[N];
void ins(int x){
circle[++cnt]=x;
rank[x]=cnt;
in_cir[x]=1;
}
void work(){
for(int i=1;i<=cnt;i++){
if(flag[circle[i]]){
pos=i;
break;
}
}
for(int i=1;i<=cnt;i++){
dis[i]=dis[i+cnt]=d[circle[i]][circle[i%cnt+1]];
}
for(int i=1;i<=cnt*2;i++){
s[i+1]=s[i]+dis[i];
}
}
void dfs(int u,int fa){
f[u]=0;
g[u]=inf;
for(auto x:e[u]){
int v=x.first,w=x.second;
if(in_cir[v]||v==fa){
continue;
}
dfs(v,u);
f[u]=max(f[u],f[v]+w);
g[u]=min(g[u],g[v]+w);
}
if(flag[u]){
g[u]=0;
}
if(f[u]+g[u]<=k){
f[u]=-inf;
}
if(f[u]+d[u][fa]>k){
f[u]=-inf;
g[u]=0;
sum++;
}
}
int solve(){
// cerr<<k<<endl;
tot=sum=0;
for(int i=1;i<=cnt;i++){
dfs(circle[i],0);
}
int fl=0;
for(int i=1;i<=cnt*2;i++){
R[i]=inf;
}
for(int i=1;i<=cnt;i++){
bool flg=0;
for(int j=1;j<=cnt;j++){
int Dis=abs(s[i]-s[j]);
Dis=min(Dis,s[cnt+1]-Dis);
if(f[circle[i]]+g[circle[j]]+Dis<=k){
flg=1;
break;
}
}
if(flg){
continue;
}
int len=k-f[circle[i]];
if(len*2>=s[cnt+1]){
if(!pos){
fl=1;
}
continue;
}
++tot;
if(s[i]+dis[cnt]>len){
seg[tot].l=1,seg[tot].r=2*cnt;
for(int j=i;j;j--){
if(s[i]-s[j]>len){
seg[tot].l=j+1;
break;
}
}
for(int j=i+1;j<=cnt*2;j++){
if(s[j]-s[i]>len){
seg[tot].r=j-1;
break;
}
}
seg[tot+1].l=seg[tot].l+cnt;
seg[tot+1].r=seg[tot].r+cnt;
++tot;
}
else{
seg[tot].l=1,seg[tot].r=2*cnt;
for(int j=i+cnt;j;j--){
if(s[i+cnt]-s[j]>len){
seg[tot].l=j+1;
break;
}
}
for(int j=i+cnt;j<=2*cnt;j++){
if(s[j]-s[i+cnt]>len){
seg[tot].r=j-1;
break;
}
}
}
}
// cerr<<tot<<' '<<fl<<endl;
if(!tot){
return sum+fl;
}
for(int i=1;i<=tot;i++){
R[seg[i].l]=min(R[seg[i].l],seg[i].r);
}
int c=0,mn=inf;
for(int i=2*cnt;i;i--){
nxt[i]=mn;
mn=min(mn,R[i]);
}
if(pos){
int x=pos;
while(nxt[x]<pos+cnt){
c++;
x=nxt[x];
}
}
else{
c=inf;
for(int i=1;i<=cnt;i++){
int x=i,S=1;
while(nxt[x]<i+cnt){
S++;
x=nxt[x];
}
c=min(c,S);
}
}
c=max(c,fl);
return sum+c;
}
}tr[N];
void visit(int u,int fa){
vis[u]=Time;
for(auto x:e[u]){
int v=x.first;
if(vis[v]==Time){
continue;
}
visit(v,u);
}
}
bool dfs(int u,int fa){
stk.push(u);
vis[u]=Time;
bool First=1;
for(auto x:e[u]){
int v=x.first;
if(vis[v]==Time){
if(v==fa){
if(First){
First=0;
continue;
}
}
while(stk.top()!=v){
tr[idx].ins(stk.top());
stk.pop();
}
tr[idx].ins(stk.top());
stk.pop();
return 1;
}
if(dfs(v,u)){
return 1;
}
}
stk.pop();
return 0;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(K);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=inf;
}
}
for(int i=1;i<=n;i++){
read(v[i]);
v[i]++;
}
for(int i=1;i<=n;i++){
read(w[i]);
e[i].pb(mp(v[i],w[i]));
e[v[i]].pb(mp(i,w[i]));
d[i][v[i]]=d[v[i]][i]=min(d[i][v[i]],w[i]);
}
for(int i=1;i<=m;i++){
int x;
read(x);
flag[x+1]=1;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
Time++;
idx++;
visit(i,0);
Time++;
dfs(i,0);
tr[idx].work();
}
}
int l=0,r=inf,ans=inf;
while(l<=r){
int mid=(l+r)>>1,x=0;
// cerr<<mid<<' ';
for(int i=1;i<=idx;i++){
tr[i].k=mid;
x+=tr[i].solve();
}
if(x>K){
l=mid+1;
}
else{
r=mid-1;
ans=mid;
}
}
write_endl(ans);
return 0;
}