关于 $10^5$ 双 $\log$ 被卡爆

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009;
const ll INF=1e18;
const ll DMa=1000000000000;
ll TOT,rt,sz[N],ma[N],dfa[N],Dis[N],son[N],p[N],dep[N],top[N],a[N],b[N],id[N];
vector<ll> to[N],w[N],ans;
bitset<N> vis;
bool show;
struct line{
	ll k,b;
	line(ll k=0,ll b=0):k(k),b(b){}
	ll val(ll x){return k*x+b;}
};
struct LiChaoTree{
	ll rt[N],rs[N*170],ls[N*170],tot=0;
	line l[N*170];
	void add(ll&x,ll Tl,ll Tr,line L){
		if(!x){x=++tot,l[x]=L;return;}
		ll mid=(Tl+Tr)>>1;
		ll pre=l[x].val(mid),now=L.val(mid);
		if(now<pre) swap(L,l[x]);
		if(Tl==Tr) return;
		pre=l[x].val(Tl),now=L.val(Tl);
		if(now<pre){add(ls[x],Tl,mid,L);return;}
		
		pre=l[x].val(Tr),now=L.val(Tr);
		if(now<pre){add(rs[x],mid+1,Tr,L);return;} 
	}
	ll query(ll x,ll Tl,ll Tr,ll k){
		if(!x) return INF;
//		if(show) cout<<l[x].k<<"x+"<<l[x].b<<"\n";
		ll mid=(Tl+Tr)>>1,val=l[x].val(k);
		if(Tl==Tr) return val;
		return min(val,k<=mid?query(ls[x],Tl,mid,k):query(rs[x],mid+1,Tr,k));
	}
}Tr;
void getRt(ll x,ll fa,ll allSz){
	if(!fa) rt=0;
	sz[x]=1,ma[x]=0;
	for(ll i=0,v;i<to[x].size();++i)
		if(!vis[v=to[x][i]]&&v^fa){
			getRt(v,x,allSz);
			sz[x]+=sz[v];
			ma[x]=max(ma[x],sz[v]);
		}
	ma[x]=max(ma[x],allSz-sz[x]);
	if(ma[x]<ma[rt]) rt=x;
}
void solve(ll x,ll allSz){
	vis[x]=1;
	for(ll i=0,v;i<to[x].size();++i)
		if(!vis[v=to[x][i]]){
			ll newSz=(sz[v]>sz[x]?allSz-sz[x]:sz[v]);
			getRt(v,0,newSz);
			dfa[rt]=x;
			solve(rt,newSz);
		}
}
void dfs1(ll x,ll fa){
	sz[x]=1;
	for(ll i=0,v;i<to[x].size();++i)
		if((v=to[x][i])^fa){
			Dis[v]=Dis[x]+w[x][i];
			dfs1(v,x);
			sz[x]+=sz[v];
			if(sz[v]>sz[son[x]]) son[x]=v;
		}
}
void dfs2(ll x,ll fa){
	p[x]=fa,dep[x]=dep[fa]+1;
	if(son[fa]==x) top[x]=top[fa];
	else top[x]=x;
	if(son[x]) dfs2(son[x],x);
	for(ll i=0,v;i<to[x].size();++i)
		if((v=to[x][i])^fa&&v^son[x])
			dfs2(v,x);
}
ll lca(ll x,ll y){
	while(top[x]^top[y]){
		ll&a=(dep[top[x]]>dep[top[y]]?x:y);
		a=p[top[a]];
	}
	return dep[x]<dep[y]?x:y;
}
ll dis(ll x,ll y){return Dis[x]+Dis[y]-2*Dis[lca(x,y)];}
/*
这道题应该是这样的
首先看到这道题是关于路径的,并且是最短路
朴素Dijkstra算法能做到O(1)进行插入,O(n)进行查边
但点分治能做到O(logn*D(x))插入,O(logn*D(x))进行查边,D(x)代表数据结构的复杂度
所以考虑用点分树去给每个路径都去找一个中转点
然后又注意到应该b应该是从大到小的,除了到最后一个城市
对于f[u],它等于min(f[v]+dis(u,v)*b[v]+a[v])
所以我们去考察f[v]+dis(u,v)*b[v]+a[v]这个量,发现f[v]要么源于b[1],要么源于b[x],其中b[x]>b[v]
所以我们可以先把1号节点插进点分树里,然后按照b从大到小把节点插入进点分树
对于中转站x,YS=f[v]+(dep[u]+dep[v])*b[v]+a[v]=dep[u]*b[v]+f[v]+dep[v]*b[v]+a[v]
	这里的dep[u]表示的是u到x的距离
	截距是f[v]+dep[v]*b[v]+a[v],斜率是b[v],横坐标是dep[u]
	先把所有直线给弄完,然后所有节点再到点分树上查找最优的一条直线
*/
bool cmp(const ll&x,const ll&y){
	return b[x]>b[y];
}
ll query(ll x){
	if(x==1) return 0;
	ll ans=dis(1,x)*b[1]+a[1],tmp=x;
//	cout<<"qry:"<<x<<"\n";
	while(x){
		ll ju=dis(x,tmp);
		ans=min(ans,Tr.query(Tr.rt[x],0,DMa,ju));
//		if(tmp==5&&x==3) show=1;
//		cout<<"  "<<x<<": "<<ju<<" "<<Tr.query(Tr.rt[x],0,DMa,ju)<<"\n";
		x=dfa[x];
//		show=0;
	}
	return ans;//这边return的ans代表从1开始只走b减小的路径,最短距离
}
void add(ll x,ll val){
	ll tmp=x;
	while(x){
		ll ju=dis(x,tmp);
		line l=(line){b[tmp],val+ju*b[tmp]+a[tmp]};
//		cout<<"Tree "<<x<<" "<<b[tmp]<<"x+"<<val<<" "<<ju*b[tmp]+a[tmp]<<"\n";
		Tr.add(Tr.rt[x],0,DMa,l);
		x=dfa[x];
	}
}
vector<long long> travel(vector<long long> A, vector<int> B, vector<int> U, vector<int> V, vector<int> W){
	ma[0]=INF;
	ll n=A.size();
	for(ll i=1;i<=n;++i) a[i]=A[i-1],b[i]=B[i-1],id[i]=i;
	for(ll i=0;i<n-1;++i){//全部加上1
		ll u=U[i]+1,v=V[i]+1,we=W[i];
		to[u].push_back(v);w[u].push_back(we);
		to[v].push_back(u);w[v].push_back(we);
	}
	getRt(1,0,n);
	solve(rt,0);
	dfs1(1,0);
	dfs2(1,0);
//	for(ll i=1;i<=n;++i,cout<<"\n")
//		for(ll j=1;j<=n;++j)
//			cout<<dis(i,j)<<" ";
//	cout<<"===============\n";
//	for(ll i=1;i<=n;++i)
//		cout<<dfa[i]<<" ";
//	cout<<"\n";
	sort(id+1,id+n+1,cmp);
	for(ll i=1;i<=n;++i){
		ll x=id[i],now=query(x);
		add(x,now);
	}
//	ans.resize(n-1);
	ans.clear();
	for(ll i=2;i<=n;++i)
		ans.push_back(query(i));
//		ans[i]=query(i+2);
	return ans;
}
//int main(){
//	freopen(".in","r",stdin);
//	cin>>TOT;
//	vector<ll> a;
//	vector<int> b,u,v,w;
//	a.resize(TOT);
//	b.resize(TOT);
//	u.resize(TOT-1);
//	v.resize(TOT-1);
//	w.resize(TOT-1);
//	for(ll i=0;i<TOT;++i) cin>>a[i];
//	for(ll i=0;i<TOT;++i) cin>>b[i];
//	for(ll i=0;i<TOT-1;++i){
//		cin>>u[i]>>v[i]>>w[i];
//	}
//	vector<ll> lst=travel(a,b,u,v,w);
//	for(ll i=0;i<lst.size();++i)
//		cout<<lst[i]<<" ";
//	return 0;
//}