城市网络

第一行，两个正整数 n , q (2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5)。第二行，n 个正整数 a_i (1 ≤ a_i ≤ 10^5) 描述每个城市售卖的珠宝的价值。接下来 n-1 行，每行描述一条道路 x , y (1 ≤ x,y ≤ n)，表示有一条连接 x 和 y 的道路。接下来 q 行，每行描述一次行程 u , v , c (1 ≤ u,v ≤ n , 1 ≤ c ≤ 10^5)。

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 2792K, 提交时间: 2020-03-30 13:09:22

 #include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
int u,v,c;
int par[100005];
vector<int> G[100005];
void dfs(int u,int v){
    par[u]=v;
    for(auto i:G[u]){
        if(i!=v) dfs(i,u);
    }
}
int cal(int u,int v,int c){
    int num=0;
    while(u!=v){
        if(a[u]>c){
            c=a[u];
            num++;
        }
        u=par[u];
    }
    if(a[v]>c) num++;
    return num;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    int t1,t2;
    for(int i=0;i<n-1;i++){
        cin>>t1>>t2;
        G[t1].push_back(t2);
        G[t2].push_back(t1);
    }
    //preprocess
    dfs(1,0);
    while(q--){
        cin>>u>>v>>c;
        cout<<cal(u,v,c)<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 352K, 提交时间: 2019-09-28 14:08:42

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int s[100001];
int value[100001];
int tmp = 0;
void dfs(int u, int des, int val);
int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", &value[i]);
	for (int i = 1; i < n; i++)
	{
		int parent, son;
		cin >> parent >> son;
		s[parent] += s[son];
		s[son] = parent;
	}
	for (int i = 1; i <= q; i++) {
		int u, des, val;
		tmp = 0;
		cin >> u >> des >> val;
		dfs(u, des, val);
		cout << tmp<<endl;
	}
}

void dfs(int u, int des, int val)
{
	if (u != des)
	{
		if (value[u] > val) {
			val = value[u];
			tmp++;
		}
		dfs(s[u], des, val);
	}
	if (value[u] > val)
		tmp++;
}

详情