树上摘樱桃

const readline = require("readline")
 
const rl = readline.createInterface({
  input:process.stdin,
  output: process.stdout
})
 
const rows = []
let m, n// 节点数 边数
const obj = {}
let result = 0
 
rl.on("line", line => {
  rows.push(line)
  if (rows.length === 1) {
    const arr1 = line.trim().split(" ").map(item => parseInt(item))
    m = arr1[0]
  } else {
    const arr2 = line.trim().split(" ").map(item => parseInt(item))
    if (!obj[arr2[0]]) obj[arr2[0]] = []
    obj[arr2[0]].push(arr2[2])
  }
  if (rows.length === m) {
    // console.log(obj)
    for(let key in obj) {
      if (obj[key].length == 2 && obj[obj[key][0]] != 0 && !obj[obj[key][1]] != 0) {
        result += 1
      }
    }
    console.log(result)
    rows.length = 0
  }
})

#include<iostream>
#include<vector>
#include<string>
using namespace std;
 
class Node{
public:
    Node *left = NULL, *right = NULL;
};
 
int numOfCherries(Node* root){
    if(!root) return 0;
    if(!root->left) return numOfCherries(root->right);
    if(!root->right) return numOfCherries(root->left);
    if(!root->left->left && !root->left->right && !root->right->left && !root->right->right) return 1;
    return numOfCherries(root->left) + numOfCherries(root->right);
}
 
int main(){
    int m, n;
    cin >> m >> n;
    //用vector里的index表示id，因为id从1开始，所以size为m+1
    vector<Node*> a(m+1);
    for(int i = 0; i < m+1; i++){
        a[i] = new Node();
    }
    for(int i = 0; i < n; i++){
        int id;
        cin >> id;
        string position;
        cin >> position;
        int child;
        cin >> child;
        if(position[0] == 'l'){
            a[id]->left = a[child];
        }
        else{
            a[id]->right = a[child];
        }
    }
    cout << numOfCherries(a[1]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int id;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _id) : id(_id), left(nullptr), right(nullptr) {}
};

int main() {
    int m, n;
    cin >> m >> n;
    int id1, id2;
    string relationship;
    // 为了节点id直接和下标对应，增加一个，不使用0下标
    vector<TreeNode*> nodes(m + 1, nullptr);
    while (cin >> id1 >> relationship >> id2) {
        if (nodes[id1] == nullptr) {
            TreeNode* node = new TreeNode(id1);
            nodes[id1] = node;
        }
        if (nodes[id2] == nullptr) {
            TreeNode* node = new TreeNode(id2);
            nodes[id2] = node;
        }
        if (relationship == "left") {
            nodes[id1]->left = nodes[id2];
        } else {
            nodes[id1]->right = nodes[id2];
        }
    }
    int count = 0;
    for (int i = 1; i < nodes.size(); ++i) {
        auto node = nodes[i];
        if (node->left != nullptr && node->right != nullptr) {
            if (node->left->left == nullptr && node->left->right == nullptr &&
               node->right->left == nullptr && node->right->right == nullptr) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

// 判断子节点是否作为父节点出现过
#include <iostream>
#include <vector>
using namespace std;


int main(){
    int nums = 0;
    int node = 0;
    cin >> nums >> node;
    int ans = 0;
    vector<vector<int>> leaves(nums + 1);
    int a = 0;
    int b = 0;
    string pos;
    for(int i = 0; i < node; ++i){
        cin >> a >> pos >> b;
        leaves[a].push_back(b);
    }

    for(auto i : leaves){
        if(i.size() == 2){
            if(leaves[i[0]].empty() && leaves[i[1]].empty()){
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}

// 子结构的数量的充分必要条件是node可以作为两个节点的父节点，且这两个节点没有对应的子节点。
// 不用创建树，使用两个哈希表
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin >> m >> n;
    unordered_map<int, pair<int,int>> children;
    unordered_map<int,int> parent;
    for(int i = 0 ;i < n;i++)
    {
        int a,b;
        string str;
        cin >> a >> str >> b;
        if(children.find(a) == children.end())
            children[a] = make_pair(b, 0xffffff);
        else
            children[a].second = b;
        parent[a]++;
    }
    int ret = 0;
    for(auto it = children.begin(); it != children.end(); it++)
        if(it->second.second != 0xffffff)
            if(parent.find(it->second.first) == parent.end() && parent.find(it->second.second) == parent.end())
                ret++;
    cout << ret << endl;
    return 0;
}

import java.util.*;
public class Test {



    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String number = sc.nextLine();
        String[] numbers = number.split(" ");
        int n = Integer.parseInt(numbers[0]);
        int sides = Integer.parseInt(numbers[1]);
        int[][] nums=new int[n + 1][2];
        int[] sons = new int[n + 1];
        int count = 0;
        for (int i = 0; i < sides; i++) {
            String str = sc.nextLine();
            String[] strs = str.split(" ");
            int index = Integer.parseInt(strs[0]);
            int sonIndex = Integer.parseInt(strs[2]);
            sons[index]++;
            if ("left".equals(strs[1])){
                nums[index][0] = sonIndex;
            }else nums[index][1] = sonIndex;
        }
        for (int i = 1; i < n+1; i++) {
            if (sons[i] == 2) {
                if (sons[nums[i][0]] == 0 && sons[nums[i][1]] == 0){
                    count++;
                }
            }
        }
        System.out.println(count);

    }




}

#include<stdio.h>
typedef struct BiTnode{
	int lchild;
	int rchild;
	int id;
	
	//int *parent;
}BiTnode,BiTree;
int main(void){
	int m;	int n; char temp;	int left;	int right;
	scanf("%d",&m);	scanf("%c",&temp);	scanf("%d",&n);
	BiTree a[m+1];
	for(int i=0;i<m+1;i++){
		a[i].id=0;
		a[i].lchild=0;
		a[i].rchild=0;
	}
	//printf("%d\t",a[2].id);printf("%d\t",a[2].lchild);printf("%d\t",a[2].rchild);
	for(int i=0;i<n;i++){
		int num;	char str[4];
		scanf("%d",&num);
		scanf("%s",str);
//		printf("%s",str);
		//a[i]->id=i;
		a[num].id=num;
//		printf("%s",str);
		if(str[0]=='l'){
//			printf("%s",str);
			scanf("%d",&left);
			//printf("%d\n",left);
			a[num].lchild=left;
		//	printf("%d",a[1].lchild);
		}else if(str[0]=='r'){
			scanf("%d",&right);
			a[num].rchild=right;
			//printf("%d",a[num].rchild);
		}
	}
	int number=0;
	for(int i=0;i<m;i++){
		//printf("123");
		if((a[i].lchild!=0)&&(a[i].rchild!=0)&&(a[a[i].lchild].lchild==0)&&(a[a[i].lchild].rchild==0)&&(a[a[i].rchild].lchild==0)&&(a[a[i].rchild].rchild==0))
		{
			number++;
			//printf("123");
	}	
	}
	/*printf("%d\t",a[1].lchild);
	printf("%d\t",a[1].rchild);
	
	printf("%d\t",a[a[1].lchild].lchild);printf("%d\t",a[a[1].lchild].rchild);
	
	printf("%d\t",a[a[1].rchild].lchild);printf("%d\t",a[a[1].rchild].rchild);*/
	printf("%d",number);
	return 0;
}

m,n=map(int,input().strip().split())

class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
tmp=[]
for i in range(n):
    father,direction,son=input().strip().split()
    tmp.append((int(father),direction,int(son)))
used=[None for _ in range(m+1)]
for bian in tmp:
    father,direction,son=bian
    if not used[father]:
        root=TreeNode()
        used[father]=root
    else:
        root=used[father]
    if not used[son]:
        node=TreeNode()
        used[son]=node
    else:
        node=used[son]
    if direction=='left':
        root.left=node
    else:
        root.right=node
ret=0
def dfs(root):
    global ret
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    l=dfs(root.left)
    r=dfs(root.right)
    if l==1 and r==1:
        ret+=1
    return l+r+1
dfs(used[1])
print(ret)
       

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.*;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String firstLine = sc.nextLine();
            String[] nums = firstLine.split(" ");
            int m = Integer.parseInt(nums[0]);
            int n = Integer.parseInt(nums[1]);
            int[] degree = new int[m + 1];
            Arrays.fill(degree,0);
            Map<Integer,Integer> fathers = new HashMap<>();
            for(int i = 0 ;i < n;i ++) {
                String line = sc.nextLine();
                String[] segs = line.split(" ");
                int parent = Integer.parseInt(segs[0]);
                int son = Integer.parseInt(segs[2]);
                degree[parent] ++;
                fathers.put(son,parent);
            }
          int[] arr = IntStream.range(1,m + 1)
                    .filter(i -> degree[i] == 0)
                    .map(e -> fathers.get(e)).toArray();
          long ret = IntStream.of(arr).count()
                   - IntStream.of(arr).distinct().count();
          System.out.println(ret);
        }
    }
}

//C++,2ms
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int edge,res = 0;  //res为结果
    cin>>edge>>edge;  //不需要节点数,只需要边的个数
    vector<int> n(2*edge); //每条边俩节点,都依次添加进vector中
    string str;  //凑数用的,用来去掉left和right
    
    int k=0;
    for(int i=0; i<edge; i++)   //把所有节点放进去(会有重复)
        cin>>n[k++]>>str>>n[k++]; //n:{1,2,1,3,2,4,2,5......}类似这样
    
    for(int i=0; i < n.size();)
    {
        if(n[i]==n[i+2]) //这个if测试节点的左右是否都有子节点
        {
            if(i == n.size()-4 || n[i+4]!=n[i+1] && n[i+4]!=n[i+3])
            {//这个测试左右子节点有没有子节点,即测试原节点是否有孙节点
                res++;
                i+=4;
            }
            else
                i+=4;
        }
        else
            i+=2;
    }
    
    cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    int nodeNum,lineNum;
    int res=0;
    vector<int> fatherVec;
    vector<int> sonVec;
    cin >> nodeNum;
    cin >> lineNum;
    while(lineNum--)
    {
        string RelaPos;
        int father, son;
        cin >> father;
        cin >> RelaPos;
        cin >> son;
        fatherVec.push_back(father);
        sonVec.push_back(son);
    }
    int index=sonVec.size()-1;
    while(index-1>=0)
    {
        if(fatherVec[index]==fatherVec[index-1] && (count(fatherVec.begin(),fatherVec.end(),sonVec[index])==0) &&
        (count(fatherVec.begin(),fatherVec.end(),sonVec[index-1])==0))
            res++;
        index--;
    }
    cout << res << endl;
    return 0;
}