笔记

其实并没有什么好记的

Luogu B3861 子树和

其实这题非常的简单，我也就不想说啥了

// 我想用C风格写代码（虽然vector不该出现，但确实这样会更节省空间）
#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
vector<int>son[N];
int f[N],n;
int dfs(int root){
    if(f[root] != -1){
        return f[root];
    }
    if(root > n){
        return 0;
    }
    f[root] = 1;
    for(int g:son[root]){
        f[root] += dfs(g);
    }
    return f[root];
}

int main(){
    // freopen("1.in","r",stdin);
    memset(f,-1,sizeof f);
    scanf("%d",&n);
    for(int i = 2;i <= n;i++){
        int x;
        scanf("%d",&x);
        son[x].push_back(i);
    }
    for(int i = 1;i <= n;i++){
        printf("%d\n",dfs(i));
    }
    return 0;
}

Luogu P5908 猫猫和企鹅

这题也是不想多说

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
vector<int>tr[N];
bool vis[N];
int d,ans;
void dfs(int x,int m){
    if(vis[x]){
        return;
    }
    if(m > d){
        return;
    }
    vis[x] = true;
    ans++;
    for(int g:tr[x]){
        dfs(g,m+1);
    }
}

int main(){
    int n;
    scanf("%d%d",&n,&d);
    for(int i = 1;i < n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1,0);
    printf("%d",ans-1);
    return 0;
}

Luogu P1364 医院设置

（看了题解）由于数据范围不大,可以把树当图做，直接 Floyd做出最短路，然后暴力一下

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int w[N],dist[N][N];
vector<int>tu[N];

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            dist[i][j] = 1e9;
        }
        dist[i][i] = 0;
    }
    for(int i = 1;i <= n;i++){
        int l,r;
        scanf("%d%d%d",&w[i],&l,&r);
        tu[i].push_back(l);
        tu[i].push_back(r);
        tu[r].push_back(i);
        tu[l].push_back(i);
        if(l != 0){
            dist[i][l] = dist[l][i] = 1;
        }
        if(r != 0){
            dist[i][r] = dist[r][i] = 1;
        }
    }
    for(int k = 1;k <= n;k++){
        for(int i = 1;i <= n;i++){
            if(i == k){
                continue;
            }
            for(int j = 1;j <= n;j++){
                if(j == i || j == k){
                    continue;
                }
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    int ans = INT_MAX;
    for(int i = 1;i <= n;i++){
        int sum = 0;
        for(int j = 1;j <= n;j++){
            sum += w[j]*dist[i][j];
        }
        ans = min(ans,sum);
    }
    printf("%d",ans);
    return 0;
}