[GESP六级] 树上漫步题解

先看题目，问的是可以结束漫步的节点数量，一般就是用DFS暴力搜，用vis记录访问过的节点，再动态求数量，此处说可以经过重复节点，所以不能用此方法。
做题要认真，先看数据切入：
40%的数据n≤10³，说明可以用n²暴力做
此题最大输入个数为2×1e5，为了让时间更短，我们使用手写快速读

template<typename T>//此处为可省略部分，为了让int和long long类型能同时用read读取
inline void read(T &x){//如果没写上一行，就要说明x是什么类型
    char ch=getchar();
    int f=1;
    x=0;
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;//负数
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(x-'0');
        ch=getchar();
    }
}//此处使用了引用，可以不用返回x

于是就有了10分代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    char ch=getchar();
    int f=1;
    x=0;
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
constexpr int N=1e3+1;
vector<int> e[N];
int n,dist[N],ans;
void dfs(int u,int fa){
    if(dist[u]%2==0) ans++;
    for(int v:e[u]){
        if(v==fa) continue;
        dist[v]=dist[u]+1;
        dfs(v,u);
    }
}
int main(void){
    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u); read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        ans=0;
        memset(dist,-1,sizeof dist);
        dist[i]=0;
        dfs(i,-1);
        cout<<ans<<" ";
    }
    cout<<"\n";
    return 0;
}

而满分代码就需要一点推理
注意到：样例的输出为一个1，其余全部为节点数量-1
于是我们可以通过画图，找到一些规律：
当两个节点间对的距离为奇数（即边数）那么就不满足条件；而当节点间的距离为偶数，那么计数器加加。
所以我们可以将本题看成是树上的染色问题，将树上的节点看成两类，一类为1，另一类为0，如果这个点的颜色为0，那么输出cnt0;如果为1，那就输出cnt1。
满分代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x){
    char ch=getchar();
    int f=1;
    x=0;
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
constexpr int N=2*1e5+1;
int n,col[N],cnt0,cnt1;
vector<int> e[N];
void dfs(int u,int fa,int c){
    if(c%2==0) cnt0++;
    else cnt1++;
    col[u]=c;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u,1-c);
    }
}
int main(){
    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u); read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,-1,0);
    for(int i=1;i<=n;i++){
        if(col[i]==1) cout<<cnt1<<" ";
        else cout<<cnt0<<" ";
    }
    return 0;
}