| 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=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int first[maxn],next[maxn<<1],to[maxn<<1],dis[maxn<<1],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 0; return 1; } 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]=1;int maxs=0; 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]=1;tot=0;dfs(x,0,0); rep(i,1,tot) id[i]=i; sort(id+1,id+tot+1,cmp); int tmp=tot;tot=0; rep(i,1,tmp) if(better(num[id[i]],A[tot])) A[++tot]=num[id[i]],B[tot]=dep[id[i]]; rep(i,1,tmp) for(int j=first2[num[i]];j;j=Q[j].next) { int l=1,r=tot+1; while(l+1<r) { int mid=l+r>>1; 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[0]=s[to[i]];getroot(to[i],root=0); solve(root); } } int main() { n=read(); rep(i,1,n) val[i]=read(); rep(i,2,n) AddEdge(read(),read(),read()); q=read(); rep(i,1,q) AddQuery(i,read(),read()); size=f[0]=n;getroot(1,0); solve(root); rep(i,1,q) printf("%d ",ans[i]); return 0; }