| WZJ的数据结构（负三十四） |
| 难度级别：C； 运行时间限制：20000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
给一棵n个节点的树，请对于形如"u r"的Q个询问, 回答以 u 节点为中心，半径 r 以内的节点中，权值最大的节点的编号是多少。如果有多个节点，返回编号最小的。
|
|
输入
|
|
共有一组测试数据。
第一行包含一个整数 n (1 ≤ n ≤ 10^5)，表示节点总数。 接下来的一行，包含 n 个数字，表示每个节点的权值 vi (1 ≤ vi ≤ 10^6)。 接下来的 n-1 行，每行三个整数 (ai, bi, wi)，表示一条连接 ai, bi 节点的边，边长为 wi(1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 3)。 接下来的一行包含一个整数 q，表示询问总数（1 ≤ q ≤ 10^5）。 接下来 q 行，每行包含两个整数 u, r(1 ≤ u ≤ n, 0 ≤ r ≤300)，表示询问以 u 节点为中心，半径 r 以内的节点中，权值最大的节点的编号是多少。如果有多解返回编号最小的。 |
|
输出
|
|
对于每组询问，输出一行表示对应答案。
|
|
输入示例
|
|
7
1 2 3 4 5 6 7 1 2 1 2 3 1 2 4 1 1 5 1 5 6 1 5 7 1 4 1 1 1 2 2 1 2 2 |
|
输出示例
|
|
5
7 4 5 |
|
其他说明
|
|
样例很邪恶哦。
|
考虑用点分治离线来解决这道题，那么问题转换成怎么解决过重心x的询问Max(val[y]|depx+depy<=r)。
我们可以用往常的做法，维护dep、val同时递增的决策序列，这个可以用平衡树来做，然后正反扫一遍。
但其实没有必要，注意x、y在同一棵子树并不会影响答案（想一想，为什么），所以只需离线构出决策序列然后二分就行了。
#include<cstdio>
#include<cctype>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int first[maxn],next[maxn<<],to[maxn<<],dis[maxn<<],e;
void AddEdge(int w,int v,int u) {
to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;
to[++e]=u;dis[e]=w;next[e]=first[v];first[v]=e;
}
int n,q,val[maxn],ans[maxn];
int better(int x,int y) {
if(val[x]<val[y]||(val[x]==val[y]&&x>y)) return ;
return ;
}
void relax(int& x,int y) {if(better(y,x)) x=y;}
struct Query {
int x,r,id,next;
}Q[maxn];
int first2[maxn],cnt;
void AddQuery(int id,int r,int x) {
Q[++cnt]=(Query){x,r,id,first2[x]};first2[x]=cnt;
}
int vis[maxn],f[maxn],s[maxn],size,root;
void getroot(int x,int fa) {
s[x]=;int maxs=;
ren if(to[i]!=fa&&!vis[to[i]]) {
getroot(to[i],x);
s[x]+=s[to[i]];maxs=max(maxs,s[to[i]]);
}
f[x]=max(maxs,size-s[x]);
if(f[root]>f[x]) root=x;
}
int tot,num[maxn],dep[maxn],id[maxn],A[maxn],B[maxn];
void dfs(int x,int fa,int D) {
num[++tot]=x;dep[tot]=D;
ren if(to[i]!=fa&&!vis[to[i]]) dfs(to[i],x,D+dis[i]);
}
int cmp(int x,int y) {return dep[x]<dep[y]||(dep[x]==dep[y]&&val[num[x]]>val[num[y]]);}
void solve(int x) {
vis[x]=;tot=;dfs(x,,);
rep(i,,tot) id[i]=i;
sort(id+,id+tot+,cmp);
int tmp=tot;tot=;
rep(i,,tmp) if(better(num[id[i]],A[tot])) A[++tot]=num[id[i]],B[tot]=dep[id[i]];
rep(i,,tmp) for(int j=first2[num[i]];j;j=Q[j].next) {
int l=,r=tot+;
while(l+<r) {
int mid=l+r>>;
if(B[mid]<=Q[j].r-dep[i]) l=mid;
else r=mid;
}
if(B[l]<=Q[j].r-dep[i]) relax(ans[Q[j].id],A[l]);
}
ren if(!vis[to[i]]) {
size=f[]=s[to[i]];getroot(to[i],root=);
solve(root);
}
}
int main() {
n=read();
rep(i,,n) val[i]=read();
rep(i,,n) AddEdge(read(),read(),read());
q=read();
rep(i,,q) AddQuery(i,read(),read());
size=f[]=n;getroot(,);
solve(root);
rep(i,,q) printf("%d\n",ans[i]);
return ;
}