atcoder beginner contest 239 E题

题目复制过来有点问题,我这边以截图的形式上传。

atcoder beginner contest 239 E题

atcoder beginner contest 239 E题 

题目的意思是建立一棵树,也就是二叉树,然后找寻某一节点下(包括此节点)的所有节点第k大,需要利用vector以及algorithm中的sort的从大到小排。我不知道能否用链式前向星,我没试过,应该也是可以的,不过这题排序的话,用vector比较合适,具体的易错点都以注释的形式写在代码中,这题是比较裸的二叉树类题(图论),适合初学者。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=2e5+10;
vector<int>e[M];//存数(图)
vector<int>subtree[M];//存子树
int n,q;//n为节点数,q为查询数
int x[M];//各个节点的值
int a1,b1;//一条边的两个节点
int i;
void dfs(int u,int parent)//子节点,父节点
{
    subtree[u].push_back(x[u]);//插入自身,不要忘了
    for(auto v:e[u])//开始遍历u的子节点
    {
        if(v==parent)continue;//因为双向存储当然会存在节点的子节点是父节点
        dfs(v,u);
        for(auto x:subtree[v])subtree[u].push_back(x);//插入子节点的子节点
    }
    sort(subtree[u].begin(),subtree[u].end(),greater<int>());
    if(subtree[u].size()>20)subtree[u].resize(20);//题目说了ki最大是20
}
int main()
{
 //使用stl语言我觉得用c语言输入输出较快
 scanf("%d%d",&n,&q);
 for(i=1;i<=n;i++)
 {
     scanf("%d",&x[i]);
 }
 for(i=1;i<n;i++)//树只有n-1条边
 {
     scanf("%d%d",&a1,&b1);
     e[a1].push_back(b1);
     e[b1].push_back(a1);//无向边的双向存储
 }
 dfs(1,0);//从1节点开始搜索,0代表此时的父亲节点,因为0不存在
 while(q--)
 {
     int v1,k1;
     scanf("%d%d",&v1,&k1);
     printf("%d\n",subtree[v1][k1-1]);//减去1的原因是因为vector是和数组类似,从0开始计算的
 }
    return 0;//完结撒花
}

上一篇:vue 微信授权


下一篇:注解@RequestParam(required = false,defaultValue =xx)