Wa 0 pts 主席树求调
查看原帖
Wa 0 pts 主席树求调
754310
Pepsee楼主2024/3/15 15:43
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int n,q,cnt;
int head[100005],tot,Siz;
int st[100005][21],lg[100005];
struct node{
	int nex,to,v,w,v2;
}edge[200005];
inline void add(int x,int y,int v1,int v2,int w)
{
	edge[++tot].nex = head[x];
	edge[tot].to = y; edge[tot].v = v1;
	edge[tot].v2 = v2; edge[tot].w = w;
	head[x] = tot;
}
inline int min(int a,int b){
	return a<b?a:b;
}
//-----------------SEGMENTTREE-------------------
int root[100005];
struct segt{
	int ls,rs;
	int val;
}tr[10000005];
void pushup(int rt){
	tr[rt].val = tr[tr[rt].ls].val+tr[tr[rt].rs].val;
}
int build(int rt,int l,int r)
{
	rt = ++cnt;
	if (l == r) return rt;
	int mid = (l+r) >> 1;
	build(tr[rt].ls,l,mid);
	build(tr[rt].rs,mid+1,r);
	return rt;
}
int insert(int rt,int l,int r,int x,int v)
{
	int u = ++cnt;	
	if(l > r) return u;
	tr[u] = tr[rt];
	if (l == r){
		tr[u].val += v;
		return u;
	}
	int mid = (l+r) >> 1;
	if (x <= mid) tr[u].ls = insert(tr[u].ls,l,mid,x,v);
	else tr[u].rs = insert(tr[u].rs,mid+1,r,x,v);
	pushup(u);
	return u;
}
int query(int rt1,int rt2,int rt3,int l,int r,int x,int y)
{
//	cout<<l<<" "<<r<<" "<<x<<" "<<y<<endl;
	if (l > r ) return 1e18;
	int res = 0;
	if (l >= x && r <= y)
		return tr[rt1].val+tr[rt2].val-2*tr[rt3].val;
	int mid = (l+r) >> 1;
	if (x <= mid) res += query(tr[rt1].ls,tr[rt2].ls,tr[rt3].ls,l,mid,x,y);
	if (y > mid) res += query(tr[rt1].rs,tr[rt2].rs,tr[rt3].rs,mid+1,r,x,y);
	return res;
}
//----------------????----------------------
int f[100005][21],dep[100005],sep[100005],pos[100005];
void dfs(int x,int fa)
{
	root[x] = insert(root[fa],1,Siz,pos[x],sep[x]);
	f[x][0] = fa; dep[x] = dep[fa]+1;
	for (int i = 1; i <= 20; i++)
		f[x][i] = f[f[x][i-1]][i-1],st[x][i] = min(st[x][i-1],st[f[x][i-1]][i-1]);
	for (int i = head[x]; i; i = edge[i].nex)
	{
		if (edge[i].to == fa) continue;
		int to = edge[i].to,v1 = edge[i].v,v2 = edge[i].v2,w = edge[i].w;
		st[to][0] = v2; sep[to] = w; pos[to] = v1;
		dfs(to,x);
	}
}
int Fi(int x,int y,int pd)
{
	int res = 1e9;
	if (dep[x] < dep[y]) swap(x,y);
	while (dep[x] > dep[y])
		res = min(res,st[x][lg[dep[x]-dep[y]]]),x = f[x][lg[dep[x]-dep[y]]];
	for (int i = 20; i; i--)
		if (f[x][i] != f[y][i])
			res = min(res,min(st[x][i],st[y][i])),x = f[x][i],y = f[y][i];
	if (x == y && !pd) return x;
	if (x == y && pd) return res;
	if (!pd) return f[x][0];
	res = min(res,min(st[x][0],st[y][0]));
	return res;
}
//-----------------------------------------
int search(int x,int y,int v)
{
	int Lca = Fi(x,y,0);
	if (v <= 0) return 0;
	int res = query(root[x],root[y],root[Lca],1,Siz,1,v);
	return res;
}
int x[100005],y[100005],v[100005],c[100005],s[100005];
int tmp[200005],cot,tru[100005];
signed main()
{
	n = read();
	for (int i = 0; i <= n; i++)
		lg[i] = log2(i);
	for (int i = 1; i < n; i++)
	{
		x[i] = read(); y[i] = read();
		v[i] = read(); c[i] = read(); s[i] = read();
		tmp[++cot] = v[i]; tmp[++cot] = s[i];
	}
	sort(tmp+1,tmp+cot+1);
	Siz = unique(tmp,tmp+cot)-tmp-1;
	for (int i = 1; i < n; i++)
	{
		int val = v[i],val2 = s[i];
		v[i] = lower_bound(tmp+1,tmp+Siz+1,val)-tmp;
		s[i] = lower_bound(tmp+1,tmp+Siz+1,val2)-tmp;
		tru[v[i]] = val; tru[s[i]] = val2;
		add(x[i],y[i],v[i],s[i],c[i]); add(y[i],x[i],v[i],s[i],c[i]);
	}
	root[0] = build(root[0],1,Siz);
	dfs(1,0);
	q = read();
	for (int i = 1; i <= q; i++)
	{
		int x = read(),y = read(),p = read();
		int r = Fi(x,y,1),l = 1,ans;
		while (l <= r)
		{
			int mid = (l+r) >> 1;
			if (search(x,y,mid-1) > p)
				r = mid-1;
			else
				ans = mid,l = mid+1;
		}
		write(tru[ans]); puts("");
	}
	return 0;
}
2024/3/15 15:43
加载中...