libreoj 6192 「美团 CodeM 复赛」城市网络 题解

发表于 | 阅读次数：
本文字数： 1.2k 字 | 阅读时长 ≈ 6 分钟

题意简述

有 $n$ 个城市，组成一张树形网络。第 $i$ 个城市售卖价值为 $a_i$ 的珠宝。zps 的父母计划了 $q$ 次行程。每次先带上价值为 $c$ 的珠宝，从城市 $u$ 走到城市 $v$ （保证 $v$ 在 $u$ 到 $1$ 的路径上）。如果当前的城市售卖的珠宝比手头的贵（严格大于，等于不行），那么 zps 的父母会买入这个珠宝。

对于每次行程，求出 zps 的父母进行了多少次“买入”操作。

$n,q,c,a_i\le 10^5$，$1\le u,v\le n$

思路

我们发现，对于每一次行程，除了第一次要特判一下之外，我下一次走到哪里应该是固定的。

假设我们当前在 $u$，那么我们下一次走的位置，应该就是 $u$ 往上跳，第一个 $a_i>a_u$ 的 $i$（当然，如果这个 $i$ 跳到了 $v$ 外面，那么我们不算它）

于是我们考虑，先用倍增求出第一个 $a_i>a_u$ 的 $i$，然后重新建图，把 $u$ 直接连到 $i$ 上。这样，对于每次行程，我们把首尾特判掉之后，就相当于新树上求一段路径的长度了。这个直接维护一个深度就能求了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    int I()
    {
        int x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        return (x=(f==1)?x:-x);
    }
    void Rd(int cnt,...)
    {
        va_list args; va_start(args,cnt);
        F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
        va_end(args);
    }
    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[N<<1];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    
    int n,m;
    int a[N];
    void Input()
    {
        Rd(2,&n,&m);
        F(i,1,n) a[i]=I();
        G.clear();
        F(i,1,n-1)
        {
            int u,v; Rd(2,&u,&v); G.Add2(u,v);
        }
    }

    int deep[N],fa[N][22],Max[N][22];
    void DFS(int u,int f)
    {
        deep[u]=(u==f)?0:deep[f]+1;
        fa[u][0]=f; F(i,1,20) fa[u][i]=fa[fa[u][i-1]][i-1];
        Max[u][0]=max(a[u],a[f]); F(i,1,20) Max[u][i]=max(Max[u][i-1],Max[fa[u][i-1]][i-1]);
        Tra(i,u) if (v!=f) DFS(v,u);
    }
    int PathMax(int u,int f) // 求路径最大值
    {
        if (u==f) return a[u];
        int ans=0;
        D(i,20,0) if (deep[fa[u][i]]>=deep[f]) 
        {
            ans=max(ans,Max[u][i]),u=fa[u][i];
        }
        
        return ans;
    }
    int MaxPos(int u,int f) // 求路径最大值是哪个位置
    {
        int Mx=PathMax(u,f);
        if (a[u]==Mx) return u;
        D(i,20,0) if (Max[u][i]<Mx) u=fa[u][i]; 
        return fa[u][0];
    }
    int FirstBig(int u,int c) // 找到 u 往上第一个满足 a[i]>c 的
    {
        if (a[u]>c) return u;
        if (Max[u][20]<=c) return n+1;
        D(i,20,0) if (Max[u][i]<=c) u=fa[u][i];
        return fa[u][0];
    }
    namespace Re_build // 把重新建的图封装起来，避免名字冲突
    {   
        Graph G;
        int deep[N],fa[N][22];
        void Init()
        {
            G.clear();
            F(i,1,n) G.AddEdge(fa[i][0],i); 
        }
        void DFS(int u)
        {
            deep[u]=(u==n+1)?0:deep[fa[u][0]]+1;
            F(i,1,20) fa[u][i]=fa[fa[u][i-1]][i-1];
            Tra(i,u) DFS(v);
        }
        int  Query(int u,int fu) {return deep[u]-deep[fu];}
    }
    void Soviet()
    {
        DFS(1,1);
        F(i,1,n) Re_build::fa[i][0]=(Max[i][20]==a[i])?n+1:FirstBig(i,a[i]);
        // 重新设置 fa 数组
        Re_build::Init();
        Re_build::DFS(n+1);
        // 重新 DFS 一遍

        F(i,1,m)
        {
            int u,v,c; Rd(3,&u,&v,&c); 
            int uu=u,vv=v; // 存储原始的 u,v (后面会有修改)
            if (u==v) {puts(c<a[u]?"1":"0"); continue;}
            if (c>=PathMax(u,v)) {puts("0"); continue;}
            u=FirstBig(uu,c);  // 先跳到上面第一个 >c 的 （注意，这里先跳了一次，所以答案+1）
            v=MaxPos(uu,vv); // 处理一下开头结尾
            printf("%d\n",Re_build::Query(u,v)+1); 
            // 如上面所说，答案 +1
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w