COJ966 WZJ的数据结构(负三十四)

时间:2024-01-16 12:05:26
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 ;
}