本文主要是介绍19082 中位特征值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【2022】贝壳找房秋招测试开发工程师笔试卷2
给你一棵以T为根，有n个节点的树。（n为奇数）每个点有一个价值V，并且每个点有一个特征值P。 每个点的特征值P为：以这个点为根的子树的所有点（包括根）的价值的和。 现在牛牛想知道这n个点对应的特征值的中位数是多少，你能告诉牛牛吗？
输入格式
第一行两个正整数，分别代表T和n。n<=1e5 接下来一行共n个正整数，分别代表编号为i的点的价值V[i]。V[i]<=1e9 接下来n-1行，每行两个正整数u,v，代表u和v之间有一条边相连。
输出格式
输出一行，共一个正整数，代表n个点特征值的中位数是多少。
输入样例
2 5 1 10 100 1000 10000 1 2 3 2 3 4 5 3
输出样例
10000
提示
根据题意，2是树根，可以先画出这棵树理解题意。点1对应的特征值为1，点2对应的特征值为11111， 点3对应的特征值为11100，点4对应的特征值为1000，点5对应的特征值为10000，中位数是10000。 提示，数据范围为1e9，那么求和计算很可能超过int范围，因此数据定义时要使用long long 类型。
题目分析：树要用图的存储方法，当然对于图结构来说并无“根”这个概念，所以任何一点都可以是树根，此题目指定某点T为根。存储时注意，需要用无向图的方式存储，因为数据并没明确指出“边”的两个点那个点是父节点。
一个树的权值和为所有结点权值和，这类用递归算法很容易实现（图的深度优先搜索算法）。
此处给出了两种递归算法中避免重复访问的方式，一种是用图算法中的标志数组V，另一种是树结构的专用写法，参数中传递父节点信息，这样递归时不会回溯，也能避免重复访问。
（1）用标志数组V避免重复访问
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,v[100005],a[100005];
long long ans[100005];
vector<int> e[100005];
long long dfs(int cur)
{v[cur]=1;ans[cur]=a[cur];for(int i=0;i<e[cur].size();i++){ int y=e[cur][i];if(v[y]==0)/**< cur..i有边，且y没有访问过 */ans[cur]+=dfs(y);}return ans[cur] ;
}
int main()
{ios::sync_with_stdio(false);int i,j,T,x,y;cin>>T>>n;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=n-1;i++){cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}dfs(T);sort(ans+1,ans+n+1);cout<<ans[n/2+1];return 0;
}（2）
(2)不用v数组的写法，递归时记录父节点
#include <bits/stdc++.h>//ASI
typedef long long ll;
using namespace std;
int T,n,v[500005];
ll ans[500005];
vector<int>e[500005];
ll dfs(int cur,int f)
{/**< 一个基础的深搜，搜索过程中去累加子树的和 */ans[cur]=v[cur];for(int i=0;i<e[cur].size();i++)if(e[cur][i]!=f) //父节点不递归ans[cur]+=dfs(e[cur][i],cur);return ans[cur];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0);int i,j,x,y;cin>>T>>n;for(i=1;i<=n;i++)cin>>v[i];for(i=1;i<n;i++){/**< 虽然是树结构，但无法确认x和y谁是父节点，一般来说树的题目都用图结构存储 */cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}dfs(T,0);sort(ans+1,ans+n+1);cout<<ans[n/2+1];/**< 题目告知n是奇数 */return 0;
}
这篇关于19082 中位特征值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
