旅游

C++ 解法, 执行用时: 130ms, 内存消耗: 25848KB, 提交时间: 2021-11-26

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+1000;
int n,s,f[N][2];
int ver[N],nxt[N],head[N],tot;
inline void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
inline void dfs(int x,int fa)
{
    f[x][1]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        f[x][1]+=f[y][0];
        f[x][0]+=max(f[y][0],f[y][1]);
    }
}
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(s,0);
    printf("%d",f[s][1]);
    return 0;
}

C++ 解法, 执行用时: 153ms, 内存消耗: 25720KB, 提交时间: 2022-01-26

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=500000 + 5;
int n,s,f[MAX_N][2];
int Last[MAX_N],Next[MAX_N<<1],End[MAX_N<<1],tot;
void addedge(int x,int y){
    End[++tot]=y;
    Next[tot]=Last[x];
    Last[x]=tot;
}
void solve(int x,int fa){
    for(int i=Last[x];i;i=Next[i]){
        int y=End[i];
        if(y!=fa){
            solve(y,x);;
            f[x][1]+=f[y][0];
            f[x][0]+=max(f[y][0],f[y][1]);
        }
    }
    f[x][1]++;
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    solve(s,0);
    printf("%d\n",f[s][1]);
    return 0;
}

C++ 解法, 执行用时: 155ms, 内存消耗: 17656KB, 提交时间: 2021-11-12

#include <bits/stdc++.h>
using namespace std;
//邻接表纪录树 边的编号从1开始
const int N=500001;
struct L{
    int head[N]={},nxt[N<<1]={},v[N<<1]={},lh=0;
    void push(int h,int val){
        nxt[++lh]=head[h];head[h]=lh;
        v[lh]=val;
    }
}l1;
int main(){
    int n,s;cin>>n>>s;
    //输入路网
    for(int i=0;i<n-1;i++){
        int a,b;scanf("%d%d",&a,&b);
        l1.push(a, b);l1.push(b, a);
    }
    //根节点为s 开始树形dp
    int dp[N][2]={};//dp[i][0]表示不取的最大值 dp[i][1]表示取到的最大值
    //非递归解法：
    struct D{int father,cur;bool recf;}st[N];int sth=0;
    st[sth++]={0,s,0};
    while(sth){
        D&cur=st[sth-1];
        if(!cur.recf){
            cur.recf=1;
            for(int i=l1.head[cur.cur];i!=0;i=l1.nxt[i])
                if(l1.v[i]!=cur.father)
                    st[sth++]={cur.cur,l1.v[i],0};
        }else{
            int f=cur.father,i=cur.cur;
            dp[i][1]+=1;
            dp[f][0]+=max(dp[i][0],dp[i][1]);
            dp[f][1]+=dp[i][0];
            sth--;
        }
    }
    printf("%d",dp[s][1]);
    return 0;
}

C++ 解法, 执行用时: 162ms, 内存消耗: 25724KB, 提交时间: 2022-07-10

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
const int N = 500000 + 5; 
const int M = N  << 1;
int  h[N], ne[M], e[M], idx;
int dp[N][2];
void add(int x, int y) {
    e[++idx] = y;
    ne[idx] = h[x];
    h[x] = idx;
}

void solve(int x, int from) {
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y != from) {
            solve(y, x);
            dp[x][1] += dp[y][0];
            dp[x][0] += max(dp[y][0], dp[y][1]);
        }
    }
    dp[x][1]++;
}
int main() {
    int n, s;
    cin >> n >> s;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    solve(s, 0);
    printf("%d\n",dp[s][1]);
    return 0;
}

C 解法, 执行用时: 171ms, 内存消耗: 21804KB, 提交时间: 2021-12-07

#include <stdio.h>

int dp[500001][2]={[0 ... 500000]={0,1}};

int next_edge=0;
int head[500001]={[0 ... 500000]=-1};
struct {
    int value;
    int next;
}edge[1000002]={[0 ... 1000001]={0,-1}};

void addEdge(int x,int y)
{
    edge[++next_edge].value = y;
    edge[next_edge].next = head[x];
    head[x] = next_edge;
}

void dfs(int x,int father)
{
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        if(edge[i].value == father) continue;
        dfs(edge[i].value,x);
        dp[x][1] += dp[edge[i].value][0];
        dp[x][0] += dp[edge[i].value][0]>dp[edge[i].value][1]?dp[edge[i].value][0]:dp[edge[i].value][1];
    }
}

int main()
{
    int n,s,x,y;
    scanf("%d %d",&n,&s);
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&x,&y);
        addEdge(x,y);
        addEdge(y,x);
    }
    dfs(s,-1);
    printf("%d",dp[s][1]);

    return 0;
}

详情