c++小池学长是学校的风云人物所以他人对他的追捧对他来说积极重要。小池学长每个月都要巩固一个交际圈表示学校中的人际关系但是他的魅力有限不能得到所有人的追捧所以只能吸引能够接触到的人。比如1认识22认识3那么1也可以接触到3。小池学长非常的smart他想知道和谁交朋友获得的追捧最多。而你是学校里第一smart的student你需要告诉他能获得最大追捧度是多少。小池学长的编号是1可能存在自环。输入格式

这是一个图的问题，可以使用图的遍历算法来解决。

首先，我们可以使用邻接表来表示学校人员的关系。对于每个人，我们可以使用一个包含他的朋友的列表来表示他的邻居节点。

接下来，我们可以使用深度优先搜索（DFS）来遍历图，并计算每个节点的追捧度。对于每个节点，我们可以遍历它的邻居节点，并更新邻居节点的追捧度为当前节点的追捧度加上与邻居节点交朋友所需要的魅力值。

最后，我们找到追捧度最大的节点，并输出它的追捧度。

以下是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int charm; // 学生的魅力值
    int popularity; // 学生的追捧度
    vector<int> friends; // 学生的朋友列表
};

void dfs(vector<Node>& nodes, int index, int charm, int popularity) {
    nodes[index].charm = charm;
    nodes[index].popularity = popularity;
    
    for (int i = 0; i < nodes[index].friends.size(); i++) {
        int neighbor = nodes[index].friends[i];
        int newCharm = nodes[index].charm + nodes[neighbor].charm;
        int newPopularity = nodes[index].popularity + nodes[neighbor].popularity;
        
        if (newPopularity > nodes[neighbor].popularity) {
            dfs(nodes, neighbor, newCharm, newPopularity);
        }
    }
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int N, M, C;
        cin >> N >> M >> C;
        
        vector<Node> nodes(N + 1);
        
        for (int i = 1; i < N; i++) {
            int a, b;
            cin >> a >> b;
            nodes[i].charm = a;
            nodes[i].popularity = b;
        }
        
        for (int i = 0; i < M; i++) {
            int x, y;
            cin >> x >> y;
            nodes[x].friends.push_back(y);
        }
        
        dfs(nodes, 1, C, 0);
        
        int maxPopularity = 0;
        for (int i = 1; i <= N; i++) {
            maxPopularity = max(maxPopularity, nodes[i].popularity);
        }
        
        cout << maxPopularity << endl;
    }
    
    return 0;
}

复杂度分析：

• 时间复杂度：由于每个节点只会被遍历一次，所以总的时间复杂度为O(N+M)，其中N为学生的数量，M为学校人员的关系数。
• 空间复杂度：使用了一个大小为N+1的vector来存储每个节点的信息，所以总的空间复杂度为O(N)。