solution
倍增思想。
用st[i][j]表示从i号节点进行次购买所到达的节点。这个可以通过一遍dfs预处理出来。关键在于怎么找st[i][0],这个可以通过i号节点的父亲进行转移。具体参考代码。
然后考虑对于一次询问,找到u到根路径上比c大的深度最大的点。先跳到这个点然后不断向上跳,一直跳到v即可。
复杂度
code
/* * @Author: wxyww * @Date: 2020-04-02 19:59:55 * @Last Modified time: 2020-04-02 20:39:22 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 100010,logN = 20; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt; }e[N << 1]; int head[N],ejs; void add(int u,int v) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs; } int fa[N],a[N],st[N][logN + 2],dep[N]; void dfs(int u,int father) { fa[u] = father; dep[u] = dep[father] + 1; if(a[father] > a[u]) st[u][0] = father; else { int x = father; for(int i = logN;i >= 0;--i) if(a[st[x][i]] <= a[u]) x = st[x][i]; st[u][0] = st[x][0]; } for(int i = 1;i <= logN;++i) st[u][i] = st[st[u][i - 1]][i - 1]; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(v == father) continue; dfs(v,u); } } int main() { int n = read(),Q = read(); for(int i = 1;i <= n;++i) a[i] = read(); for(int i = 1;i < n;++i) { int u = read(),v = read(); add(u,v);add(v,u); } a[0] = 1e9; dfs(1,0); while(Q--) { int u = read(),v = read(),c = read(); int x = u; if(a[x] <= c) { for(int i = logN;i >= 0;--i) if(a[st[x][i]] <= c) x = st[x][i]; x = st[x][0]; } int ans = 0; // if(dep[x] == dep[v]) ans = 1; // else if(dep[x] >= dep[v]) { for(int i = logN;i >= 0;--i) { if(dep[st[x][i]] >= dep[v]) { x = st[x][i]; ans += 1 << i; } } ans += 1; } printf("%d\n",ans); } return 0; }