当前位置 博文首页 > 文章内容

    城市网络

    作者: 栏目:未分类 时间:2020-07-27 11:00:20

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    城市网络

    Problem:

    有一个树状的城市网络(即 n 个城市由 n-1 条道路连接的连通图),首都为 1 号城市,每个城市售卖价值为 a_i 的珠宝。
    你是一个珠宝商,现在安排有 q 次行程,每次行程为从 u 号城市前往 v 号城市(走最短路径),保证 v 在 u 前往首都的最短路径上。 在每次行程开始时,你手上有价值为 c 的珠宝(每次行程可能不同),并且每经过一个城市时(包括 u 和 v ),假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀(价值更高,即严格大于),那么你就会选择购入。
    现在你想要对每一次行程,求出会进行多少次购买事件。

    Input:

    第一行,两个正整数 \(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)\)

    Output:

    对于每次行程输出一行,为所购买次数。

    Example:

    Input

    5 4
    3 5 1 2 4
    1 2
    1 3
    2 4
    3 5
    4 2 1
    4 2 2
    4 2 3
    5 1 5
    

    Output

    2
    1
    1
    0
    

    题解:

    树上倍增,ST表,由于每次经过一个城市我们都会选择是否购买珠宝,决策后手上的珠宝都是经过路径上价值最大的珠宝,所以我们需要知道在需要经过的路径上,珠宝价值不断递增的城市有多少,本题如果用暴力方法,最差情况下会是O(n*q)的时间复杂度,显然这是不行的。本体应该用st表去维护每个节点上需要经过几个不断递增的节点,st表的递推式:

    \[st[i][j]=st[st[i][j-1]][j-1] \]

    \(st[i][j]\)表示从i点开始能买\(2^j\)个珠宝的点是哪个,所以如果一直\(st[i][0]\)的值,那么i往上买\(2^j\)个珠宝的点,可以由i往上买\(2^j-1\)个珠宝的点再买\(2^{j-1}\)个珠宝的点,所以递推式如上。对于\(st[i][0]\)我们也可以用倍增的方式求,但是我们用从大到小枚举j值,这样就可以找到最远的可以买到1个珠宝的位置(如果枚举到的位置比当前权值小则需要继续向上倍增(倍增长度减少一半,因为原长度倍增的话则相当于已经倍增过的长度))。

    经过ST表处理后的树,对于每次查询我们只需要查询从u开始,且深度大于等于v的点数之和(映射到ST表中就是满足条件的倍增长度的总和)。

    关于ST表:https://www.cnblogs.com/LeafLove/p/12345136.html

    Code:

    /**********************************************************
    * @Author: 			   Kirito
    * @Date:   			   2020-07-27 08:15:25
    * @Last Modified by:   Kirito
    * @Last Modified time: 2020-07-27 09:27:55
    * @Remark: 
    **********************************************************/
    #include <bits/stdc++.h>
    #define lowbit(x) (x&(-x))
    #define CSE(x,y) memset(x,y,sizeof(x))
    #define INF 0x3f3f3f3f
    #define Abs(x) (x>=0?x:(-x))
    #define FAST ios::sync_with_stdio(false);cin.tie(0);
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef pair<ll , ll> pll;
    
    const int maxn=211111;
    vector<int> v[maxn];
    int a[maxn],f[maxn][20],dep[maxn],to[maxn];
    
    void dfs(int p,int fa)
    {
    	int x=fa;
    	for(int k=19;k>=0;k--){
    		if(f[x][k]&&a[f[x][k]]<=a[p]) x=f[x][k];
    	}
    	if(a[x]>a[p]) f[p][0]=x;
    	else f[p][0]=f[x][0];
    
    	for(int i=1;i<20;i++)
    		f[p][i]=f[f[p][i-1]][i-1];
    
    	dep[p]=dep[fa]+1;
    
    	for(auto t:v[p]){
    		if(t==fa) continue;
    		dfs(t,p);
    	}
    	return;
    }
    
    int n,q;
    
    int main()
    {
    	#ifndef ONLINE_JUDGE
    	freopen("in.in","r",stdin);
    	#endif
    	FAST;
    	cin>>n>>q;
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	for(int i=0;i<n-1;i++){
    		int x,y;
    		cin>>x>>y;
    		v[x].push_back(y);
    		v[y].push_back(x);
    	}
    	for(int i=n+1;i<=n+q;i++){
    		int x,y,c;
    		cin>>x>>y>>c;
    		v[i].push_back(x);
    		v[x].push_back(i);
    		a[i]=c;
    		to[i-n]=y;
    	}
    	dfs(1,0);
    	for(int i=1;i<=q;i++){
    		int ans=0;
    		int x=i+n;
    		for(int k=19;k>=0;k--){
    			if(dep[f[x][k]]>=dep[to[i]]){
    				ans+=(1<<k);
    				x=f[x][k];
    			}
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }