性感整体二分,0pts求调
查看原帖
性感整体二分,0pts求调
656765
STARSczy楼主2024/3/14 16:58

rt.

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define per(i,r,l) for(int i=(r),i##end=(l);i>=i##end;--i)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10,maxm=60+10,mod=1e9+7;

int n,q,idtt,dep[maxn],fa[maxn],sz[maxn],hs[maxn],lt[maxn],id[maxn];
int up[maxm],t[maxm][maxn];
vector<int> e[maxn];
priority_queue<pair<int,int>> pq[maxm];
struct qst{int id,u,v,x,ans,w;}a[maxn];
struct edge{int u,v,vp,c,vn;}bg[maxn];
void dfs1(int x){
	sz[x]=1;
	for(int u:e[x]) if(u!=fa[x]){
		fa[u]=x,dep[u]=dep[x]+1,dfs1(u),sz[x]+=sz[u];
		if(sz[u]>sz[hs[x]]) hs[x]=u;
	}
}
void dfs2(int x){
	if(!lt[x]) lt[x]=x;
	lt[hs[x]]=lt[x],id[x]=++idtt;
	if(hs[x]) dfs2(hs[x]);
	for(int u:e[x]) if(u!=fa[x]&&u!=hs[x]) dfs2(u);
}
int check(int cnt,int u,int v){
	int ans=0;
	while(lt[u]!=lt[v]){
		if(dep[lt[u]]<dep[lt[v]]) swap(u,v);
		for(int i=id[u];i;i-=i&-i) ans+=t[cnt][i];
		for(int i=id[lt[u]]-1;i;i-=i&-i) ans-=t[cnt][i];
		u=fa[lt[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	for(int i=id[v];i;i-=i&-i) ans+=t[cnt][i];
	for(int i=id[u];i;i-=i&-i) ans-=t[cnt][i];
	return ans;
}
void solve(int cnt,int x,int y,int l,int r){
	if(l>r||x>y) return;
	int mid=l+r>>1,mp=y;
	for(int &i=up[cnt];bg[i].vp<mid&&i<n;++i){
		if(dep[bg[i].u]<dep[bg[i].v]) swap(bg[i].u,bg[i].v);
		for(int j=id[bg[i].u];j<=n;j+=j&-j) t[cnt][j]+=bg[i].c;
		for(pq[cnt].push({-bg[i].vn,bg[i].u});pq[cnt].size()&&-pq[cnt].top().fi<mid;pq[cnt].pop())
			for(int j=id[pq[cnt].top().se];j<=n;j+=j&-j) t[cnt][j]+=1e9;
	}
	rep(i,x,y) if(check(cnt,a[i].u,a[i].v)<=a[i].x) a[i].w=1,a[i].ans=mid;
	else a[i].w=0;
	sort(a+x,a+y+1,[&](qst a,qst b){return a.w<b.w;});
	rep(i,x,y) if(a[i].w==1) mp=i-1,i=y;
	solve(cnt+1,x,mp,l,mid-1),solve(cnt+1,mp+1,y,mid+1,r);
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	rep(i,1,n-1) cin>>bg[i].u>>bg[i].v>>bg[i].vp>>bg[i].c>>bg[i].vn,
		e[bg[i].u].push_back(bg[i].v),e[bg[i].v].push_back(bg[i].u);
	cin>>q,dfs1(1),dfs2(1),sort(bg+1,bg+n,[&](edge a,edge b){return a.vp<b.vp;});
	rep(i,1,q) cin>>a[i].u>>a[i].v>>a[i].x,a[i].id=i;
	for(int i=0;i<=60;++i) up[i]=1;
	solve(0,1,q,0,1e18),sort(a+1,a+q+1,[&](qst a,qst b){return a.id<b.id;});
	rep(i,1,q) cout<<a[i].ans<<'\n';
	return 0;
}
2024/3/14 16:58
加载中...