解题报告

可能是沙雕题，但是我又做不来又写不来QAQ。

只要求出所有直线的凸包（分界点），就可以分类讨论树上倍增搞了。

注意分界点相同标号的大小问题，处理不好就会GG。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=100000,maxm=100000,Log=17;

int n,m,Q,dep[maxn+5],ST[maxn+5][Log+5];pair<int,int> q[maxm+5];LL a[maxn+5],b[maxn+5];
int ID[maxn+5],stk[maxn+5];LL t[maxn+5];int ans[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline bool cmp(const int &A,const int &B) {return a[A]<a[B]||a[A]==a[B]&&b[A]<b[B]||a[A]==a[B]&&b[A]==b[B]&&A<B;}
void Dfs(int x,int pre=0){
    dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);for (int j=Log;dep[x]>dep[y]&&~j;j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
inline int getfa(int x,int k) {for (int j=Log;~j;j--) if (k>>j&1) x=ST[x][j];return x;}
inline DB getX(int i,int j) {return (DB)(b[j]-b[i])/(a[i]-a[j]);}
inline LL getY(int i,LL x) {return a[i]*x+b[i];}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(Q);for (int i=1;i<=n;i++) readi(b[ID[i]=i]);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),x++,y++,Add(x,y),Add(y,x);
    for (int i=1;i<=Q;i++) readi(q[q[i].sc=i].fr),q[i].fr--;sort(ID+1,ID+1+n,cmp);sort(q+1,q+1+Q);Dfs(1);
    for (int i=1;i<=n;i++){
        while (m&&(b[ID[i]]>b[stk[m]]||b[ID[i]]==b[stk[m]]&&ID[i]>stk[m])) m--;
        while (m){
            LL A=getY(stk[m],t[m]),B=getY(ID[i],t[m]);
            if (B>A||B==A&&ID[i]>stk[m]) m--; else break;
        }
        if (m){
            LL pos=getX(stk[m],ID[i]);
            if (getY(ID[i],pos)<getY(stk[m],pos)) pos++;
            if (getY(ID[i],pos)==getY(stk[m],pos)&&ID[i]<stk[m]) pos++;
            stk[++m]=ID[i];t[m]=pos;
        } else stk[++m]=ID[i];
    }
    for (int i=1;i<m;i++) t[i]=t[i+1]-1;t[m]=9e18;
    for (int i=1,x=1,j=1,lst=0;i<=Q;ans[q[i].sc]=x-1,i++)
        while (true){
            int T=min(t[j],(LL)q[i].fr)-lst+1,y=stk[j],lca=LCA(x,y),dis=dep[x]+dep[y]-(dep[lca]<<1);
            if (T>=dis) x=y; else dep[x]-dep[lca]>=T?x=getfa(x,T):x=getfa(y,dis-T);
            lst=min(t[j],(LL)q[i].fr)+1;while (t[j]<lst) j++;if (q[i].fr<lst) break;
        }
    for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);return 0;
}