【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 
#include 
#include 
using namespace std;
int n,m,v[100005],a[100005];
long long ans[100005];
vector 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)/**>T>>n;
    for(i=1;i>a[i];
    for(i=1;i>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(T);
    sort(ans+1,ans+n+1);
    cout<

（2）

(2)不用v数组的写法，递归时记录父节点
#include //ASI
typedef long long ll;
using namespace std;
int T,n,v[500005];
ll ans[500005];
vectore[500005];
ll dfs(int cur,int f)
{/**< 一个基础的深搜，搜索过程中去累加子树的和 */
    ans[cur]=v[cur];
    for(int i=0;i>T>>n;
    for(i=1;i>v[i];
    for(i=1;i<n;i++)
    {/**>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(T,0);
    sort(ans+1,ans+n+1);
    cout<