涉及知识点：图论 贪心

题意

有一颗 \(n\ (\leq 50)\) 个节点的树，节点 \(i\) 的父亲为 fa[i]，到父亲的边的边权为 dis[i]，边权 \(\leq 500\)。现在要将每个点分配到 \(k\) 个连通子图中的一个，使得子图中距离最长的两个点距离小于 \(maxd\)，定义子图为：如果 \(u\) 和 \(v\) 都是该子图的点并且原树中 \(u\) 到 \(v\) 存在边，那么子图中 \(u\) 到 \(v\) 也存在边。求出最小可能的 \(k\)。

思路

首先可以翻译一下题目，题目中对于找子图的描述是“分配”，但实际上我们会发现无论怎么分配，合法的子图一定是原树删掉某些边得到的森林，因为假设原树上两个点 \(u\) 和 \(v\) 都属于一个子图，但 \(u\) 到 \(v\)​ 到的路径上的点属于其他子图，该子图不可能连通，因此不合法。

因此我们只需要贪心断边，记 \(disf[i]\) 为 \(i\) 到其子树最远的点的距离，记录点 \(fa\) 的所有儿子的 \(disf+w\) （\(w\) 为父亲到儿子的边的边权）并从大到小排序，每次判断最大和次大加起来是否会超 \(maxd\)，如果超出则断开最大对应的点到父亲的边。

代码

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
typedef pair<int,int> pii;
const int MAXN=55,MAXD=505;
int n,fa[MAXN],dis[MAXN],maxd,f[MAXN],disf[MAXN];
vector<pii>g[MAXN];
void dfs(int x){
    vector<int>sondis;
    sondis.push_back(0);
    for(auto it:g[x]){
        if(it.first==fa[x]) continue;
        dfs(it.first);
        f[x]+=f[it.first];
        sondis.push_back(disf[it.first]+it.second);
    }
    sort(sondis.begin(),sondis.end());
    while(sondis.size()>=2 && sondis.back()+sondis[sondis.size()-2]>maxd){
        f[x]++;
        sondis.pop_back();
    }
    disf[x]=sondis.back();
}
int main(){
    rd(n);
    for(int i=1;i<=n;i++){
        rd(fa[i]); 
    }
    rd(n);
    for(int i=1;i<=n;i++){
        rd(dis[i]);
        g[fa[i]].emplace_back(i,dis[i]);
        g[i].emplace_back(fa[i],dis[i]);
    }
    rd(maxd);
    n++;
    dfs(0);
    cout<<f[0]+1<<endl;
    return 0;
}