[Writeup] RedpwnCTF

這場 CTF 我覺得難度頗高
許多題目都想了很久才做出來 (甚至是做不出來._.)

這場有趣的部分是
我們這隊好不容易在賽中 Misc 破台
我還很高興的截圖丟 FB, IG
結果過沒幾分鐘又有一題新的 Misc …
最後因為一直沒點進去最關鍵的頁面所以錯失了那題的 Flag QAQQQ

最終排名: 24 / 926 (1000 分以上的分界在第 155 名)
這場我只貢獻 10 / 29 題 (隊友貢獻 19 題 <(_ _)> )
拿了 2538 分

有別於以往,這篇我只會丟我認為比較難 / 有趣的

[Web] blueprint - 168pts

Written by: ginkoid

All the haxors are using blueprint. You created a blueprint with the flag in it, but the military-grade security of blueprint won’t let you get it!

blueprint.tar.gz

Solution

首先可以先把檔案在本地架起來並觀察一下他在做的事

  1. / 會列出所有 public 為 true 的 blueprints
  2. /make 會 POST contentpublic ,但是真正儲存的只有 public ,因為後端的 content 被打成 cоntent 了 ( o 不同)
  3. POST 過後會跳到 /blueprints/:id:id 為該 blueprint 的 id

最一開始我在想會不會是跟 js 特性有關的題目
雖然方向正確但是卻是在 Google 這題用到的 package 的時候才發現

package.json :

{
"name": "blueprint",
"version": "0.0.0",
"private": true,
"dependencies": {
"lodash": "4.17.11",
"mustache": "^3.0.1",
"raw-body": "^2.4.1"
}
}

我發現除了 lodash 外,其他的都有指定某個版本以上
唯獨 lodash 指定了 4.17.11
查了一下發現 lodash4.17.11 有 Prototype Pollution 的漏洞
可以利用 js 的 prototype 將 public 從 undefined 變為 true
如此在回到 / 的時候,含有 flag 的第一個元素就會因為 public 為 true 而被列出來了

Prototype Pollution

先來看兩張圖吧

如右圖所示,增加了一行 a.constructor.prototype.public = true ,再 new 一個 Object 出來,他的 public 就變成 true 了

Why?

這是因為一個叫 Prototype 的東西,它是一個 function 的”原型”,所有為該類型的變數都會擁有 prototype 內的一切東西,包括 function, variable 等
上圖在做的事是在 object 的 prototype 中,建立一個變數叫做 public ,並將他的值設為 true
之後如果再 new Object 出來,該變數之 public 就會被設為 true

lodash 中的 defaultsDeep() 在做的事就是將後面的 object merge 到前面的 object 中
也就是說我們可以使他 merge 一個 prototype 進去,使得該類型內變數的值可控
在此題即是將 public 設為 true
payload: {"constructor": {"prototype": {"public": true}}}

(其實應該還要再提一下 constructor 才對,不過我有點懶,所以關於 constructor 的部分就去看 這篇文章 吧XD)

Flag flag{8lu3pr1nTs_aRe_tHe_hiGh3s1_quA11tY_pr0t()s}

[Forensics] Molecule Shirts - 212pts

Written by: NotDeGhost

Apparently, this picture has a name? The flag is in the format flag{name}.

picture.png

Solution

這題最一開始應該很多人會想成 Steganography 的題目吧 (包括我)
不過後來突然想到官方有提到這場有一個題型叫做 OSINT (Open Source Intelligence)
然後我就把圖片拿去以圖搜圖了

沒意外的話結果應該會跑出一家商店的網站 www.cafepress.com
裡頭會看到許多印有分子的商品
且每一個分子都會有一個自己的名字

接下來的步驟就是砸時間在上面找了

Flag flag{Dr. Armstrong}

[Forensics] Dedication - 388pts

Written by: Tux

Only for the dedicated.

chall.zip

Solution

將題目給的 zip 解壓縮後會有一個資料夾,裡面有一個 png 檔跟一個有密碼保護的 zip 檔
將 png 用文字編輯器打開會發現他給了 600 × 400 的 RGB 數對
可以先用 PIL 將它轉成圖片再想下一步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from PIL import Image
import sys

W, H = 600, 400

img = Image.new('RGB', (W, H))
pix = img.load()

f = open(sys.argv[1], 'r').read().replace('\n', '').split(' ')

cnt = 0
for i in range(W):
for j in range(H):
r, g, b = map(int, f[cnt][1:-1].split(','))
pix[i, j] = (r, g, b)
cnt += 1

img.save('res.png')

轉換後的結果:

不難發現這應該就是該 zip 檔的密碼

解壓縮後會發現是一直在做同樣的事
於是我寫了一個 script 來跑

有幾點要注意到的是

  1. 我用是 GOCR ,但是對於圖中的字體他有時會解讀錯誤
    所以我選擇先將解讀出來的密碼存在 password.txt
    若解壓縮的過程中出了錯誤,就手動更改 password.txt 裡的 password 再繼續 script
  2. 注意到 Line 11 使用 GOCR 的部分後面 pipe 了一堆 tr ,其原因同前述
    • 該字體之 g 有時會判別不出來而變成 _
    • 對於大小寫相像的字母像是 s, w ,有時會判斷成大寫
    • 有時會莫名的出現多餘的空格或是換行
    • (GOCR -c 參數的部分好像沒用…)
  3. Line 13 ~ 16 的部分我將所有形如 yxxx ,以 y 為首的字變成 xxxy ,一樣是 GOCR 辨識上的問題

接著就可以開始跑啦
(麻煩的是會一直辨識錯誤,所以要一直顧著)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#!/bin/bash

while True
do

if [ ! -e "password.txt" ]
then
python trans.py `ls | grep -oE ".*\.png"`

password=`gocr -c "abcdefghijklmnopqrstuvwxyz" res.png | tr "_" "g" | tr [:upper:] [:lower:] | tr -d " " | tr -d "\n"`

if [ ${password:0:1} == "y" ]
then
password=${password:1:${#password}}${password:0:1}
fi
printf "password = $password\n"
printf $password > password.txt
fi

unzip -P `cat password.txt` `ls | grep -oE ".*\.zip"` || exit

rm *.zip *.png *.txt

folder=`find . -mindepth 1 -maxdepth 1 -type d`
cp $folder/*.* . 2>/dev/null
rm -r $folder

done

跑完後會得到一張圖片,其內容為 flag

Flag flag{th3s_1s_tru3_d3d1cAt10N!!!}

[Reverse Engineering] JavaIsEZ - 120pts

Written by: ItzSomebody

Java RE is super ez - even a moron could do it!

JavaIsEZ.class

Solution

這題我首先找了個線上的 Decompiler 來用

Decompile 結果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package p000;

/* renamed from: JavaIsEZ */
public class JavaIsEZ {

/* renamed from: a */
private static /* synthetic */ int f0a;

/* JADX WARNING: Code restructure failed: missing block: B:20:0x0079, code lost:
if (r7.toString().equals("\u0007+?>!\u0013|CU\u0018o*\u0005M;j\ts,=\u0005M;\u0018\u000fs*h,J\u0017F0s?8\u0012#{Z\u0007:") == false) goto L_0x007b;
*/
/* JADX WARNING: Code restructure failed: missing block: B:21:0x007b, code lost:
r0 = "noob";
r1 = java.lang.System.out;
*/
/* JADX WARNING: Code restructure failed: missing block: B:22:0x0080, code lost:
r0 = "You got it right :P";
r1 = java.lang.System.out;
*/
/* JADX WARNING: Unexpected end of synchronized block */
/* Code decompiled incorrectly, please refer to instructions dump. */
public static void main(java.lang.String[] r11) {
/*
r1 = 0
r10 = 1
r2 = 0
L_0x0003:
r0 = 0
redpwnCTF_says_stop_using_ur_decompiler r0 = (redpwnCTF_says_stop_using_ur_decompiler) r0 // Catch:{ all -> 0x00ba }
java.lang.String r0 = "java.utils.ArrayList"
java.lang.Class.forName(r0) // Catch:{ all -> 0x00ba }
java.util.concurrent.ThreadLocalRandom r0 = java.util.concurrent.ThreadLocalRandom.current() // Catch:{ all -> 0x00ba }
r3 = 1
r4 = 65535(0xffff, float:9.1834E-41)
int r0 = r0.nextInt(r3, r4) // Catch:{ all -> 0x00ba }
f0a = r0 // Catch:{ all -> 0x00ba }
r0 = r1
L_0x001a:
int r4 = f0a
if (r0 == 0) goto L_0x0003
switch(r4) {
case -555: goto L_0x007b;
case 1: goto L_0x0080;
case 4882: goto L_0x0003;
default: goto L_0x0021;
}
L_0x0021:
int r0 = r11.length
int r0 = r0 + -1
if (r0 >= 0) goto L_0x0085
java.lang.String r0 = "You need to specify the flag..."
java.io.PrintStream r1 = java.lang.System.out
L_0x002a:
r1.println(r0)
return
L_0x002e:
char[] r5 = r0.toCharArray()
int r3 = r5.length
java.lang.Object r0 = new java.lang.Object
r0.<init>()
r0 = r2
L_0x0039:
int r6 = r0 - r3
if (r6 != 0) goto L_0x00b4
r0 = 8
int[] r6 = new int[r0]
r0 = 97
r6[r2] = r0
r0 = 71
r6[r10] = r0
r0 = 2
r3 = 94
r6[r0] = r3
r0 = 3
r3 = 89
r6[r0] = r3
r0 = 4
r3 = 90
r6[r0] = r3
r0 = 5
r3 = 121(0x79, float:1.7E-43)
r6[r0] = r3
r0 = 6
r3 = 72
r6[r0] = r3
r0 = 7
r3 = 53
r6[r0] = r3
java.lang.StringBuilder r7 = new java.lang.StringBuilder
r7.<init>()
r0 = r2
L_0x006d:
if (r0 == 0) goto L_0x0094
java.lang.String r3 = r7.toString() // Catch:{ IllegalMonitorStateException -> 0x00b8 }
java.lang.String r8 = "\u0007+?>!\u0013|CU\u0018o*\u0005M;j\ts,=\u0005M;\u0018\u000fs*h,J\u0017F0s?8\u0012#{Z\u0007:"
boolean r0 = r3.equals(r8) // Catch:{ IllegalMonitorStateException -> 0x00b8 }
if (r0 != 0) goto L_0x0080
L_0x007b:
java.lang.String r0 = "noob"
java.io.PrintStream r1 = java.lang.System.out
goto L_0x002a
L_0x0080:
java.lang.String r0 = "You got it right :P"
java.io.PrintStream r1 = java.lang.System.out
goto L_0x002a
L_0x0085:
r0 = r11[r2]
int r3 = r0.length()
int r3 = r3 + -42
if (r3 == 0) goto L_0x002e
java.lang.String r0 = "noob"
java.io.PrintStream r1 = java.lang.System.out
goto L_0x002a
L_0x0094:
java.util.concurrent.ThreadLocalRandom r3 = java.util.concurrent.ThreadLocalRandom.current() // Catch:{ IllegalMonitorStateException -> 0x00b8 }
r8 = 1
r9 = 65535(0xffff, float:9.1834E-41)
int r0 = r3.nextInt(r8, r9) // Catch:{ IllegalMonitorStateException -> 0x00b8 }
r3 = r2
L_0x00a1:
monitor-exit(r5) // Catch:{ IllegalMonitorStateException -> 0x00b8 }
char r8 = r5[r3] // Catch:{ IllegalMonitorStateException -> 0x00b8 }
int r9 = r6.length // Catch:{ IllegalMonitorStateException -> 0x00b8 }
int r9 = r3 % r9
r9 = r6[r9] // Catch:{ IllegalMonitorStateException -> 0x00b8 }
r8 = r8 ^ r9
char r8 = (char) r8 // Catch:{ IllegalMonitorStateException -> 0x00b8 }
r7.append(r8) // Catch:{ IllegalMonitorStateException -> 0x00b8 }
int r3 = r3 + 1
if (r4 != 0) goto L_0x0003
r0 = r2
goto L_0x00a1
L_0x00b4:
int r0 = r0 + 1
monitor-enter(r5)
goto L_0x0039
L_0x00b8:
r3 = move-exception
goto L_0x006d
L_0x00ba:
r0 = move-exception
goto L_0x001a
*/
throw new UnsupportedOperationException("Method not decompiled: p000.JavaIsEZ.main(java.lang.String[]):void");
}
}

講實話我看不懂他在幹嘛
(Line 29: redpwnCTF_says_stop_using_ur_decompiler XDD)
但是我注意到的幾個關鍵的地方就足以讓我得到 Flag 了

  • Line 10: 字串的比對,猜測應該是拿運算後的結果來比對
  • Line 62 ~ 91: 宣告了一個字元陣列
  • Line 120 ~ 132: 看起來像是在對兩個陣列做 xor

上面三點一出來大概就可以知道該怎麼做了

1
2
3
4
s = '\x07+?>!\x13|CU\x18o*\x05M;j\ts,=\x05M;\x18\x0fs*h,J\x17F0s?8\x12#{Z\x07:'
a = [97, 71, 94, 89, 90, 121, 72, 53]

print(''.join(chr(ord(j) ^ a[i % len(a)]) for i, j in enumerate(s)))

Flag flag{j4v4_1s_4s_h4rd_4s-n4t1v3_sQ4aaHZ3of}

[Misc] Tux Trivia Show - 50pts

Written by: Tux

Win Tux Trivia Show!

nc chall2.2019.redpwn.net 6001

Solution

nc 過去他會問你各國首都 (或是美國某州的主要城市)
我的做法是寫個爬蟲去爬維基的資料
維基在各國頁面的表格會有一個欄位是首都

但是會遇到不合的
例如名稱翻譯上的不同或是遷過首都的 (好像有,有點忘了)
這時候就需要自己手動查了

為了避免已經爬過的重複再爬
我選擇將已經爬好的結果存到 txt 檔裡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from pwn import *
import requests

HOST = 'chall.2019.redpwn.net'
PORT = 6001

r = remote(HOST, PORT)
r.recvline()

record = {}
with open('rec.txt', 'r') as f:
for line in f:
line = line.strip().split(':')
record[line[0]] = line[1]

for i in range(1000):
q = r.recvline()
print(q.strip())
question = q.split('of', 1)[1].split('?')[0].strip()
print(question)

if question in record:
capital = record[question]
else:
wiki = requests.get('https://en.wikipedia.org/wiki/{}'.format(question.replace(' ', '_')))
wiki = wiki.text

capital = wiki.split('>Capital<')[1].split('</a>')

if '/wiki/List' in capital[0]:
capital = capital[1]
else:
capital = capital[0]

capital = capital.split('>')[-1]

print(capital)
r.sendline(capital)

r.recvlines(2)

if question not in record:
with open('rec.txt', 'a') as fout:
fout.write(question + ':' + capital + '\n')

r.interactive()

Flag flag{TUX_tr1v1A_sh0w+m3st3r3d_:D}

[Misc] MC Password Storage - 333pts

Written by: Brownie

My friend stores his passwords in Minecraft worlds, and while he was distracted, I grabbed one of them. However, the password is encrypted. Could you help me get his password?

Note: Load the world in Minecraft Java to do the challenge

Password_Manager.zip

Solution

這題我覺得滿有趣的

一進去會發現幾個告示牌
告知你必須找到 The Decoder Wheel 的正確排列才會得到正確的密碼

建築背後有紅石電路圖

右方是 The Decoder Wheel ,按下金磚上的按鈕會順時針旋轉一格,由玻璃及混凝土組成,分別代表 0 / 1
左方那串是 Input 之一,按下建築物內的按鈕會推掉一個,由沙子及龍蛋組成,分別代表 0 / 1
後方的藍色建築是 The Logic Box 有兩個輸入及一個輸出

在測試過不同的輸入後可以確定這個邏輯閘是 xor

接著題目好像就變得沒有那麼複雜了:
暴力嘗試 The Decoder Wheel 的所有順序
將結果輸出即可

1
2
3
4
5
6
7
8
9
wheel = '00101100111'
bit = '111100000001111010101111001111101011000001010100010101100100001011010110111111111100000110100010000101001111100100000110101100110000100100010101011100111101001010101101110111101010010100001111'

for _ in range(len(wheel)):
wh = wheel[_:] + wheel[:_]
wh = wh * (len(bit) // len(wh)) + wh[:len(bit) % len(wh)]
res = [int(i) ^ int(j) for i, j in zip(bit, wh)]
res = ''.join(str(i) for i in res)
print(''.join(chr(int(res[i:i+8], 2)) for i in range(0, len(res), 8)))

(總共有 192 bit… 數得好累…)

Flag flag{m1n3cr4f7_x0r_71m3}

[Misc] l-star - 364pts

Written by: jespiron

All-star? More like L-star !!!

Note: number of states <= 10.

nc chall2.2019.redpwn.net 6002

yay.txt nay.txt l-star.c

Solution

觀察一下題目給的程式可以知道
我們要輸入一個 regular expression 的 pattern
要滿足:

  • yay.txt 中的每行都匹配到
  • nay.txt 中的每行都不匹配

在稍微觀察了一下發現 yay.txt 中的每行都是以 aba 結尾, nay.txt 則不然
於是輸入 .*aba 即可得到 flag

Flag flag{h0w_m4nY_Ls_t1l_a115t4rz}

[Misc] expobash - 442pts

Written by: fishy15

nc chall2.2019.redpwn.net 6005

problem_state.txt

Solution

題目內容大概如下:
給你兩個長度為 n 的陣列 a, b
對於所有 a 的子序列 a' ,將 a' 中的第 $i$ 個元素 xor b[i] ,並將結果加起來
求所有 a' 經上述操作的和之末 10 位

最一開始我寫了份 brute force 的程式
但是發現題目的 $n$ 會到 30 ,用 brute force 的方法需要跑 $2 ^ {30}$ 個數,雖然沒有時限,但是還是會跑很久

後來仔細想了一下
利用組合的觀點,假設 a[i] 出現在 a' 中的第 $j$ 位,即 a'[j]
可以觀察一下 a[i] 出現在第 $j$ 位之個數,如此只需計算 a[i] ^ b[j] 再乘上出現次數即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 8

cnt = [{} for i in range(1 << n)]

for i in range(1 << n):
c = 0
for j in range(n):
if i & (1 << j):
if c not in cnt[j]: cnt[j][c] = 1
else: cnt[j][c] += 1
c += 1

for i in range(n):
print('{}: {}'.format(i, cnt[i]))

Output:

0: {0: 128}
1: {0: 64, 1: 64}
2: {0: 32, 1: 64, 2: 32}
3: {0: 16, 1: 48, 2: 48, 3: 16}
4: {0: 8, 1: 32, 2: 48, 3: 32, 4: 8}
5: {0: 4, 1: 20, 2: 40, 3: 40, 4: 20, 5: 4}
6: {0: 2, 1: 12, 2: 30, 3: 40, 4: 30, 5: 12, 6: 2}
7: {0: 1, 1: 7, 2: 21, 3: 35, 4: 35, 5: 21, 6: 7, 7: 1}

冒號左邊的數字 $i$ 代表 a[i] ,右方則是 key-value 的形式
代表的是 a[i]a' 中出現在下標為 key 的次數為 value

可以觀察到第 $i + 1$ 行的第 $j$ 跟 $j + 1$ 個元素包含第 $i$ 行的一半
(有點巴斯卡三角形的味道)

接著就照著上面提到的想法
在讀入 $n$ 的時候先建好這個表格
再來就可以在 $n ^ 2$ 的時間內完成計算了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from pwn import *

HOST = 'chall2.2019.redpwn.net'
PORT = 6005

r = remote(HOST, PORT)

while True:
n = int(r.recvline().strip())
print(n)
a = map(int, r.recvline().strip().split())
print(a)
b = map(int, r.recvline().strip().split())
print(b)

m = 1 << (n - 1)
cnt = [[] for i in range(n)]

for i in range(n):
for j in range(i + 1):
cnt[i].append(0)
cnt[0][0] = m
for i in range(1, n):
for j in range(i):
cnt[i][j] += cnt[i - 1][j] // 2
cnt[i][j + 1] += cnt[i - 1][j] // 2

sum = 0
for i in range(n):
for j in range(i + 1):
sum = (sum + (a[i] ^ b[j]) * cnt[i][j]) % (10 ** 10)

res = str(sum)[-10:].zfill(10)
print(res)
r.sendline(res)

Flag flag{c4n_1_h4v3_4_c0mb_pl0x}

[Misc] mallcop - 479pts

Written by: jespiron

Help Daniel.

nc chall2.2019.redpwn.net 6003

in.zip

Solution

題目大意:
給你一棵有 $n$ 個節點的樹,有一人在其根 $k$ 上
接下來有 $n - 1$ 行,每行三個整數 $a$ $b$ $x$
代表 $a$ 到 $b$ 有一條長度為 $x$ 的邊

今欲在這棵樹的葉上設下無人機,無人機及人每分鐘可選擇前進一單位或是不動
人被抓住的條件是遇到無人機
求人在無法到達葉的情況下,最少需部署幾台無人機

我的想法如下:

定義

  1. dep[i]i 的深度
  2. deg[i]i 的度數
  3. mn[i]i 的子樹中深度最淺的葉節點編號

仔細想一下應該不難發現:
對於當前節點 $cur$ 來說,如果 $cur$ 之子樹中深度最淺的葉節點到 $cur$ 之距離小於根到 $cur$ 之距離,代表在以 $cur$ 為根的子樹中,只需在節點 mn[cur] 部署一台即可
照此想法遞迴做下去即可得到答案

註:
我在賽中的做法用了兩次 DFS
第一次是計算 depmn
第二次是計算答案
後來賽後想到,可以在計算 dep 的時候接著計算答案
這樣只要一次 DFS 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'

using namespace std;

int n, k;
map<int, int> id;
int cnt_id, res;
vector<vector<pair<int, int>>> G;
vector<int> dep, deg, mn;
vector<bool> vis;

void calc_dep(int, int);
void cnt(int);

signed main()
{
IO;
cin >> n >> k;

G.resize(n + 1);
deg.resize(n + 1);
for (int i = 1; i < n; i++) {
int a, b, x;
cin >> a >> b >> x;
if (!id[a]) {
cnt_id++; id[a] = cnt_id;
}
if (!id[b]) {
cnt_id++; id[b] = cnt_id;
}
a = id[a], b = id[b];
G[a].emplace_back(b, x);
G[b].emplace_back(a, x);
deg[a]++, deg[b]++;
}

dep.resize(n + 1);
vis.resize(n + 1);
mn.resize(n + 1);
fill(dep.begin(), dep.end(), 0);
fill(vis.begin(), vis.end(), 0);
fill(mn.begin(), mn.end(), INT_MAX);
vis[id[k]] = true;
calc_dep(id[k], 0);

fill(vis.begin(), vis.end(), 0);
vis[id[k]] = true;
for (auto i : G[id[k]]) {
vis[i.first] = true;
cnt(i.first);
}

cout << res << endl;

return 0;
}

void calc_dep(int cur, int depth)
{
dep[cur] = depth;
if (deg[cur] == 1) {
mn[cur] = depth;
return;
}
for (auto i : G[cur]) {
if (!vis[i.first]) {
vis[i.first] = true;
calc_dep(i.first, depth + i.second);
mn[cur] = min(mn[cur], mn[i.first]);
}
}
}

void cnt(int cur)
{
if (deg[cur] == 1) {
res++;
return;
}
if (deg[cur] >= 2 && mn[cur] - dep[cur] <= dep[cur]) {
res++;
return;
}
for (auto i : G[cur]) {
if (!vis[i.first]) {
vis[i.first] = true;
cnt(i.first);
}
}
}

Flag flag{0M6_th@_p0or_k1dd0}