如题，我本来使用数组模拟trie树，然后超时了，主要是我采用class封装Trie，然后在多组T时直接删了重新构造，猜测是在堆上不断分配大量内存导致超时

于是，我使用指针动态申请内存，然而，确实不超时了，但是1 和6点居然内存超限？？！！

要知道，我是使用动态分配内存！用多少开多少，怎么会比数组模拟还占空间？

修改后

#include <iostream>
#include <array>
#include <memory>

class Trie {
    struct Node {
        std::array<std::shared_ptr<Node>, 66> nxt;
        //int word = 0;
        int prefix = 0;

        Node() = default;
    };

    std::shared_ptr<Node> root;

    static int get_id(char ch) {
        if(ch >= '0' && ch <= '9') {
            return ch - '0';
        }
        if(ch >= 'A' && ch <= 'Z') {
            return ch - 'A' + 10;
        }
        if(ch >= 'a' && ch <= 'z') {
            return ch - 'a' + 36;
        }
        std::cerr << "ERROR!!!!!\n";
        return -1;
    }

public:
    Trie() : root(std::make_shared<Node>()) {
    }

    void insert(const std::string &s) const {
        auto now = root;
        for(const auto &ch: s) {
            int id = get_id(ch);
            if(now->nxt[id] == nullptr) {
                now->nxt[id] = std::make_shared<Node>();
            }
            now = now->nxt[id];
            now->prefix++;
        }
        //now->word++;
    }

    int find_prefix(const std::string &s) {
        auto now = root;
        for(const auto &ch: s) {
            int id = get_id(ch);
            if(now->nxt[id] == nullptr) {
                return 0;
            }
            now = now->nxt[id];
        }
        return now->prefix;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t;
    std::cin >> t;
    for(int i = 1; i <= t; i++) {
        int n, q;
        std::cin >> n >> q;
        auto trie = std::make_unique<Trie>();
        //Trie* trie = new Trie;
        for(int j = 1; j <= n; j++) {
            std::string tmp;
            std::cin >> tmp;
            trie->insert(tmp);
        }
        for(int j = 1; j <= q; j++) {
            std::string tmp;
            std::cin >> tmp;
            std::cout << trie->find_prefix(tmp) << '\n';
        }
        //delete trie;
    }
    return 0;
}

修改前

#include<iostream>
#include<string>
#include<array>
#include<memory>

class Trie {
	std::array<std::array<int, 62>, (size_t)2e6> tr;
	std::array<int, (size_t)2e6> prefix;
	int tot = 0;
	
	int get_id(char ch) {
		if(ch >= '0' && ch <= '9') {
			return ch - '0';
		}
		if(ch >= 'A' && ch <= 'Z') {
			return ch - 'A' + 10;
		}
		if(ch >= 'a' && ch <= 'z') {
			return ch - 'a' + 36;
		}
		std::cerr << "ERROR!!!!!\n";
	}	
public:
	void insert(const std::string &str) {
		int now = 0;
		for(const auto &ch: str) {
			int id = get_id(ch);
			if(tr[now][id] == 0) {
				tr[now][id] = ++tot;
			}
			now = tr[now][id];
			prefix[now]++;
		}
	}
	int find_prefix(const std::string &str) {
		int now = 0;
		for(const auto &ch: str) {
			int id = get_id(ch);
			if(tr[now][id] == 0) {
				return 0;
			}
			now = tr[now][id];
		}
		return prefix[now];
	}
};

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int t;
	std::cin >> t;
	for(int i = 1; i <= t; i++) {
		int n, q;
		std::cin >> n >> q;
		auto trie = std::make_unique<Trie>();
		//Trie* trie = new Trie;
		for(int j = 1; j <= n; j++) {
			std::string tmp;
			std::cin >> tmp;
			trie->insert(tmp);
		}
		for(int j = 1; j <= q; j++) {
			std::string tmp;
			std::cin >> tmp;
			std:: cout << trie->find_prefix(tmp) << '\n';
		}
		//delete trie;
	}
}