PTA 智能护理中心统计（树）-Toy模板网

这篇具有很好参考价值的文章主要介绍了PTA 智能护理中心统计（树）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

智能护理中心系统将辖下的护理点分属若干个大区，例如华东区、华北区等；每个大区又分若干个省来进行管理；省又分市，等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责，每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能，来统计任何一个管理结点所负责照看的老人的数量。

注意这是一个动态问题，即随时可能有老人加入某个管理结点，并且老人是有可能从一个管理结点换到另一个管理结点去的。

输入格式：

输入在第一行中给出 2 个正整数：N（≤10⁴ ）是老人的总数量，即老人们从 1 到 N 编号；M（≤10⁵）是归属关系的总数。

接下来是 M 行，每行给出一对归属关系，格式为：

A B

表示 A 归属于 B。A 或 B 如果是某个管理结点，则用不超过 4 个大写英文字母表示其名称；如果是某位老人，则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B，且只有这个中心系统本身是没有上级归属的。此外，输入保证没有老人自己承担管理结点的角色，即 B 一定是一个管理结点，不可能是老人的编号。但一个管理结点既可以管辖下级结点，也可以直接护理一部分老人。

随后每行给出一个指令，格式为：

指令内容
如果指令为 T，则表示有老人要入院或转院，内容是某老人的编号和要去的管理结点的名称，以空格分隔；如果指令为 Q，则内容是一个管理结点的名称，意思是统计这个结点所负责照看的老人的数量；如果指令为 E，则表示输入结束。题目保证指令总数不会超过 100 个。

输出格式：

对每个 T 指令，将对应的老人转存到对应的管理结点名下；对每个 Q 指令，在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。

输入样例：

10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E

输出样例：

题解

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author akuya
 * @create 2023-10-30-15:24
 */
public class Main {
    static int n,m;
    static Map<String,String> mp=new HashMap<>();
    static Map<String,Integer> sum=new HashMap<>();
    static Map<String,String> place =new HashMap<>();
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        String s1,s2,ts;
        while(m--!=0){
            s1=scanner.next();
            s2=scanner.next();
            if(s1.charAt(0)<'0'||s1.charAt(0)>'9'){
                mp.put(s1,s2);
                ts=s2;
                while(ts!=""){
                    sum.put(ts,sum.getOrDefault(ts,0)+sum.getOrDefault(s1,0));
                    ts=mp.getOrDefault(ts,"");
                }
            }else{
                place.put(s1,s2);
                ts=s2;
                while(ts!=""){
                    sum.put(ts,sum.getOrDefault(ts,0)+1);
                    ts=mp.getOrDefault(ts,"");
                }
            }
        }

        String s;
        s=scanner.next();
        while(!s.equals("E")){
            if(s.equals("T")){
                s1=scanner.next();
                s2=scanner.next();
                String ss=place.getOrDefault(s1,"");
                while(ss!=""){
                    sum.put(ss,sum.getOrDefault(ss,0)-1);
                    ss=mp.getOrDefault(ss,"");
                }

                place.put(s1,s2);
                ss=s2;
                while(ss!=""){
                    sum.put(ss,sum.getOrDefault(ss,0)+1);
                    ss=mp.getOrDefault(ss,"");
                }
            }else{
                s1=scanner.next();
                System.out.println(sum.getOrDefault(s1,0));
            }

            s=scanner.next();

        }

    }
}