题目分析

这是一道关于人物关系和层次结构的题目，解题的关键在于构建一个树形结构来表示人物之间的关系，并通过深度优先搜索（DFS）计算每个节点的子树大小。

题目理解

• 给定一组人物，每个人有ID、金钱和身高三个属性。
• 人物之间的关系形成一棵树，每个节点的父节点是在金钱比他多的人中，身高第一个大于等于他的人。
• 如果没有满足条件的父节点，则该节点的父节点为虚拟根节点0。
• 需要回答每个查询：某个节点的父节点ID和他的子树大小（不包括自己）。

代码实现

下面是实现该算法的代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct nod{
    int id;
    int money;
    int tall;
}ve[30010];    
map<int, int> fa;
map<int, vector<int> > son;
map<int,int> hz;

bool cmp(nod a,nod b)
{
    return a.money<b.money;
}

int dfs(int x)
{
    if(son[x].size()==0)
    {
        hz[x]=1;
        return 1;
    }
    int ans=1;
    for(int i=0;i<son[x].size();i++)
    {
        int y=son[x][i];
        ans=ans+dfs(y);
    }
    return hz[x]=ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        fa.clear();
        son.clear();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&ve[i].id,&ve[i].money,&ve[i].tall);
        }
        sort(ve,ve+n,cmp);
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(ve[i].tall<=ve[j].tall)
                {
                    fa[ve[i].id]=ve[j].id;
                    son[ve[j].id].push_back(ve[i].id);
                    break;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(fa[ve[i].id]==0)
            {
                son[0].push_back(ve[i].id);
            }    
        }
        dfs(0);
        for(int i=0;i<m;i++)
        {
            int t;
            scanf("%d",&t);
            cout<<fa[t]<<" "<<hz[t]-1<<endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：排序的时间复杂度为O(n log n)，构建树的时间复杂度为O(n²)（最坏情况），DFS的时间复杂度为O(n)，处理每个查询的时间复杂度为O(1)。总体时间复杂度为O(n²)，适用于题目给定的n≤30000的范围。

• 空间复杂度：主要使用了映射和向量存储树结构，空间复杂度为O(n)。