蚂蚁(ant)
【题目描述】
小 R 种了一棵苹果树,这棵树上有 n 个节点(标号从 0 到 n-1),有 n-1 条树枝连接这
n 个节点,这 n 个节点相互连通。每条树枝的长度为 1。
苹果树上的每一个节点上生长着一个苹果,这个苹果散发着香味。在 0 时刻,第 i 个
节点的苹果散发香味的浓郁度为 s[i],以后每过一个单位时间,香味的浓郁度就会增加 a[i]。
苹果树上还有一只蚂蚁,在 0 时刻时,这只蚂蚁在 0 号节点,在第 i 时刻,它会朝着
第 i 时刻时香味最浓郁的节点方向走 1 个单位长度。
(如果两个节点的浓郁度相同,则标号
较大的节点被认为是香味更浓郁的)
。如果在第 i 时刻,蚂蚁所处的位置已经是香味最浓郁
的节点了,那么它会选择在原地休息。
现在,小 R 有 m 个问题,他想知道在第 t[i]个时刻蚂蚁的位置。
【输入格式】
第一行 2 个整数 n,m,表示点数和询问数。
第二行 n 个整数,表示每个节点的初始香味浓郁度 s[i]。
第三行 n 个整数,表示每个节点的香味浓郁度的增加值 a[i]。
接下来 n-1 行,每行三个整数 s,t,表示 s 和 t 之间有一条边。
最后一行 m 个整数,表示 m 个询问。
【输出格式】
对于每个询问输出一行答案,表示在 t[i]时刻蚂蚁的位置。
【样例输入】
3 4
6 3 1
0 6 7
0 1
0 2
1 2 3 4
【样例输出】
0
1
0
2
【样例解释】
在 0 时刻时,0 号节点的香味最浓郁,蚂蚁原地休息,因此在 1 时刻蚂蚁仍在 0 号点
在 1 时刻时,1 号节点的香味最浓郁,蚂蚁向 1 号节点走去,因此在 2 时刻蚂蚁在 1 号点
在 2 时刻时,2 号节点的香味最浓郁,蚂蚁向 2 号节点走去,因此在 3 时刻蚂蚁在 0 号点
在 3 时刻时,2 号节点的香味最浓郁,蚂蚁向 2 号节点走去,因此在 4 时刻蚂蚁在 2 号点
【数据规模和约定】
对于 100%的数据 n<=100000,m<=100000,0<=a[i]<=10^6,0<=s[i]<=10^15,0<=t[i]<=10^9
这个题我一开始傻逼的以为是一个动态点分治,然后打了一个暴力,准备拿来对拍;
打着打着发现这是一个半平面交啊,我迟疑了一下,说好的数据结构呢???怎么没有一题要打数据结构
但是在没有办法了,于是只能拿计算几何幼儿园级别的水平硬着头皮敲了一个半平面交+暴力转移,然后调了半天,各种细节
实在是调不出来,只能再次滚粗
考完之后出题人很震惊,说T1只要是个人都应该写得出来吧!!!
好吧其实的确是的,但不过对于这道很操的细节题我也是不想说话
大体思路是这样的:
苹果的香味是一个关于时间的一次函数(很显然吧)
然后其实是要求每一个时刻苹果香味最大的苹果在哪里,并向其移动
这就很像水平可见直线了,在每个直线能被看到的那段时间就表示是会向那个点移动
(注意还有一个与水平可见直线不一样的地方:交点必须在x轴正半轴,被坑了好久;)(貌似半平面交要加一堆特判???,我记得我的斜率优化不是这样的啊!!!)
然后我们考虑到t有10^9级别,那我们就不能暴力跳了,先把询问离线排序
接着我们可以在半平面交中找出所有转折点(直线的交点),然后两个交点的每一段分段处理
在每一段上用倍增快速跳.
附上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
const int N=100050;
const int Inf=2147483647;
vector<int> p[N];
int f[N][18],deep[N],ans[N];
int n,m,u,v,t[N],tn;
struct data {
int id;
long long s,a;
} a[100100],qu[100100];
struct query {
int id,t;
} q[100100];
bool operator<(data a,data b) {
return a.a < b.a;
}
bool operator<(query a,query b) {
return a.t < b.t;
}
void dfs(int x) {
for (int i=0;i<p[x].size();i++)
if (f[p[x][i]][0]==-1) {
f[p[x][i]][0]=x;
deep[p[x][i]]=deep[x] + 1;
dfs(p[x][i]);
}
}
void pre_BZ() {
for (int i=1;i<n;i++) f[i][0]=-1;
f[0][0]=0;deep[0]=0;dfs(0);
for (int i=1;i<18;i++)
for (int j=0;j<n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int lca(int a,int b) {
if (deep[a]>deep[b]) return lca(b,a);
for (int j=17;j>=0;j--)
if (deep[b]-(1<<j) >=deep[a])
b=f[b][j];
for (int j = 17;j >= 0;j--)
if (f[a][j] != f[b][j])
a=f[a][j],b=f[b][j];
if (a != b) return f[a][0];
return a;
}
int meeting(data &a,data &b) {
if (a.a == b.a) {
if (b.s>a.s||(b.s==a.s&&b.id>a.id)) return -1;
return Inf;
}
int ans = (a.s-b.s)/(b.a - a.a) + 1;
if ((a.s-b.s)%(b.a-a.a)==0&&b.id>a.id) ans--;
if (ans<0) return -1;
if (ans>Inf) return Inf;
return ans;
}
void BPMJ() {
sort(a,a+n);int tail=0,c1,c2;
for (int i=0;i<n;i++) {
while(tail>0) {
c1=meeting(qu[tail],a[i]);
if (c1<=0) {tail--;continue;}
if(tail>1){c2=t[tail-2];if(c2>=c1){tail--;continue;}}
break;
}
qu[++tail]=a[i];
if(tail>1) t[tail-2]=c1;
}
tn=tail-1;
}
int jump(int a,int l) {
for(int j=17;j>=0;j--)
if (l>=(1<<j)) {
a=f[a][j];
l-=(1 << j);
}
return a;
}
int move(int st,int ed,int t) {
int LCA=lca(st,ed);
int l1=deep[st]-deep[LCA];
int l2=deep[ed]-deep[LCA];
if (t<=l1) return jump(st,t);
if (t<=l1+l2) return jump(ed,l1+l2-t);
return ed;
}
int gi(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void work(){
sort(q,q+m);int now=0,lastt=0,i=0,j=0;
while (j<m) {
if (t[i]<q[j].t&&i<tn) {
now=move(now,qu[i+1].id,t[i]-lastt);
lastt=t[i];i++;
}
else {
now=move(now,qu[i+1].id,q[j].t-lastt);
lastt=q[j].t;ans[q[j].id]=now;j++;
}
}
}
main() {
freopen("ant.in","r",stdin);
freopen("ant.out","w",stdout);
n=gi(),m=gi();
for(int i=0;i<n;i++) a[i].s=gi(),a[i].id=i;
for(int i=0;i<n;i++) a[i].a=gi();
for(int i=0;i<n-1;i++) {
int u=gi(),v=gi();
p[u].push_back(v);p[v].push_back(u);
}
for (int i=0;i<m;i++) q[i].t=gi(),q[i].id=i;
pre_BZ();BPMJ();work();
for (int i=0;i<m;i++) printf("%lld\n",ans[i]);
return 0;
}