首页 > 试题广场 >

旅游

[编程题]旅游

热度指数：1770 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Cwbc和XHRlyb生活在 s 市，这天他们打算一起出去旅游。

旅行地图上有 n 个城市，它们之间通过 n-1 条道路联通。

Cwbc和XHRlyb第一天会在 s 市住宿，并游览与它距离不超过 1 的所有城市，之后的每天会选择一个城市住宿，然后游览与它距离不超过 1 的所有城市。

他们不想住在一个已经浏览过的城市，又想尽可能多的延长旅行时间。

XHRlyb想知道她与Cwbc最多能度过多少天的时光呢？

聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述:

第一行，两个正整数n和s，表示城市个数和第一天住宿的城市s。
接下来n-1行，每行两个整数x和y，表示城市x与城市y之间有一条双向道路。

输出描述:

第一行，一个非负整数表示答案。

示例1

输入

输出

说明

第一天，在1号城市住宿，游览了1、2号城市。
第二天，在3号城市住宿，游览了4号城市，旅行结束。

备注:

1 ≤ n ≤ 500000, 1 ≤ s, x, y ≤ n。

算法知识视频讲解

C++

茅铁屋

状态DP+树形DP

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010, M = 2*N;
int v[M], ne[M], h[N];//用静态链表存用邻接表存储的树（实际存的是无向图）
int f[N][2];//f[i][1]表示在i城市休息时，其子树的最大值，f[i][0]反之
int idx;
//给无向图添加边
void add(int a, int b){
    v[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
//深度搜索，求状态f[i][j]的值
void dfs(int u, int father){
    f[u][0]=0;
    f[u][1]=1;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = v[i];
        if(j == father) continue;
        dfs(j, u);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0], f[j][1]);
    }
}
int main() {
    idx=0;
    memset(h, -1, sizeof h);
    int n, root;
    cin >> n >> root;
    for(int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(root, -1);
    cout << f[root][1] << endl;
    return 0;
}

发表于 2023-02-08 18:00:47 回复(0)

JayjayF

建议出题人重学语文，不知哔哔啥，这题不就是没有上司的舞会吗

发表于 2023-08-21 14:41:58 回复(0)

C++

牛客538857993号

#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 500010, M = 2 * N;
int h[N], e[M], ne[M], idx;
bool st[N];

PII dfs(int root){
    st[root] = true;
    int s = 1, t = 0;
    for(int i = h[root]; ~i; i = ne[i]){
        int u = e[i];
        if(st[u]) continue;
        PII p = dfs(u);
        s = max(s, s + p.y);
        t = max(t, max(t + p.x, t + p.y));
    }
    return {s, t};
}

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main() {
    memset(h, -1, sizeof h);
    int n, root;
    cin >> n >> root;
    int a, b;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    PII ans = dfs(root);
    cout << ans.x;
    return 0;
}
    
// 64 位输出请用 printf("%lld")

发表于 2023-01-10 18:07:27 回复(0)

LibraXiong

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int s = in.nextInt();
            HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
            for (int i = 0; i < n - 1; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                if (map.get(x) == null) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(y);
                    map.put(x, list);
                } else map.get(x).add(y);

                if (map.get(y) == null) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(x);
                    map.put(y, list);
                } else map.get(y).add(x);
            }
            int[][] dp = new int[n + 1][2];
            dfs(map, dp, s, -1);
            //System.out.println(Math.max(dp[s][0], dp[s][1])); 看清题目是s点放入 所以只有一种情况
            System.out.println( dp[s][1]);
        }
    }
    public static void dfs(HashMap<Integer, ArrayList<Integer>> map, int[][] dp,
                           int root, int pre) {
        dp[root][1] = 1;
        //root 当前结点 pre 父节点
        if (map.get(root) == null) {
            return; //叶结点
        }
        for (int i = 0; i < map.get(root).size(); i++) {
            int v = map.get(root).get(i); //子节点
            if (v == pre) continue; //找回到了根结点
            dfs(map, dp, v, root);
            dp[root][1] += dp[v][0];
            dp[root][0] += Math.max(dp[v][1], dp[v][0]);
        }
    }
}

发表于 2022-09-19 11:45:33 回复(0)

C++

牛客288355985号

极限爆内存，再多2KB就超过64MB了

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> edge[500009];
vector<int> childs[500009];
bool p[500009];
int dpnone(int);
int dphave(int);

void bfs_tree(int start){
  queue<int> bfs;
  bfs.push(start);
  while(!bfs.empty()){
    int curr=bfs.front();
    for(auto node:edge[curr]){
      if(p[node]==0){
        p[node]=1;
        childs[curr].push_back(node);
        bfs.push(node);
      }
    }
    bfs.pop();
  }
}

int main(){
  int n,s;
  cin>>n>>s;
  p[s]=1;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  bfs_tree(s);
  cout<<dphave(s)<<endl;
}

int dpnone(int node){
  static int cache[500009];
  if(cache[node]) return cache[node];
  int result=0;
  for(int child:childs[node]){
    result+=max(dphave(child),dpnone(child));
  }
  return cache[node]=result;
}

int dphave(int node){
  static int cache[500009];
  if(cache[node]) return cache[node];
  int result=1;
  for(int child:childs[node]){
    result+=dpnone(child);
  }
  return cache[node]=result;
}

发表于 2022-09-03 23:59:06 回复(0)

C++

MC枫少

#include<bits/stdc++.h>

usingnamespacestd;

constintMAX_N=500000 + 5;

intn,s,f[MAX_N][2];

intLast[MAX_N],Next[MAX_N<<1],End[MAX_N<<1],tot;

voidaddedge(intx,inty){

End[++tot]=y;

Next[tot]=Last[x];

Last[x]=tot;

}

voidsolve(intx,intfa){

for(inti=Last[x];i;i=Next[i]){

inty=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]++;

}

intmain(){

scanf("%d%d",&n,&s);

for(inti=1;i<n;i++){

intx,y;

scanf("%d%d",&x,&y);

addedge(x,y);

addedge(y,x);

}

solve(s,0);

printf("%d\n",f[s][1]);

return0;

}

发表于 2022-07-11 14:53:15 回复(0)

C++

Scarecrow928

cpp的vector在容量较大时，如果size == capacity需要分配更多内存，再次分配的空间是当前内存乘2，那个50w的用例可能一下次会分配太多😅

发表于 2021-12-20 16:43:50 回复(0)

牛客760622808号

python 第11个用例超时，不知道为什么，，

def ans():
    num, start = map(int, input().split(" "))
    tree = {start:[]}
    for _ in range(num-1):
        t1, t2 = map(int, input().split(" "))
        if t1 in tree:
            tree[t1].append(t2)
        else:
            tree[t1] = [t2]
        if t2 in tree:
            tree[t2].append(t1)
        else:
            tree[t2] = [t1]
    dp = [[0,1] for _ in range(num+1)]
    def dfs(cur, pre):
        for next in tree[cur]:
            if next == pre:
                continue
            dfs(next,cur)
            dp[cur][1] += dp[next][0]
            dp[cur][0] += max(dp[next][0], dp[next][1])
    dfs(start,-1)
    print(dp[start][1])
ans()

发表于 2021-11-04 11:29:06 回复(0)