結果
問題 | No.806 木を道に |
ユーザー |
![]() |
提出日時 | 2019-03-22 22:19:08 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 176 ms / 2,000 ms |
コード長 | 2,610 bytes |
コンパイル時間 | 3,856 ms |
コンパイル使用メモリ | 113,292 KB |
実行使用メモリ | 48,544 KB |
最終ジャッジ日時 | 2024-09-19 05:49:28 |
合計ジャッジ時間 | 3,816 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;class Program{public class Node{public int id;public List<Node> link = new List<Node>();public Node(int i){id = i;link = new List<Node>();}}static void connect (Node a, Node b){a.link.Add(b);b.link.Add(a);return;}static void Main(string[] args){int n = int.Parse(Console.ReadLine());List<Node> nodes = new List<Node>();for (int i=0; i<n; i++) nodes.Add(new Node(i));for (int i=0; i<n-1; i++){string[] s = Console.ReadLine().Split(' ');connect(nodes[int.Parse(s[0]) - 1], nodes[int.Parse(s[1]) - 1]);}int[] searchList = new int[n];for(int i=0; i<n; i++) searchList[i] = -1;List<int> queue = new List<int>();queue.Add(0);searchList[0] = 0;int lastId = 0;/*while(queue.Count > 0){int id = queue[0];foreach(Node node in nodes[id].link){if (searchList[node.id] < 0){searchList[node.id] = searchList[id] + 1;queue.Add(node.id);}}lastId = id;queue.Remove(id);}//Console.Error.WriteLine(lastId);int start = lastId;queue.Add(lastId);for(int i=0; i<n; i++) searchList[i] = -1;searchList[lastId] = 0;while(queue.Count > 0){int id = queue[0];foreach(Node node in nodes[id].link){if (searchList[node.id] < 0){searchList[node.id] = searchList[id] + 1;queue.Add(node.id);}}lastId = id;queue.Remove(id);}//Console.Error.WriteLine(start + " " + lastId + " " + searchList[lastId]);Console.WriteLine(n - 1 - searchList[lastId]);*/int ans = 0;foreach(Node node in nodes){if (node.link.Count > 2) ans += node.link.Count - 2;}Console.WriteLine(ans);}}//mcs Main.cs//mono Main.exe