Submission #1331107

#TimeUsernameProblemLanguageResultExecution timeMemory
1331107boclobanchatTwo Currencies (JOI23_currencies)C++20
100 / 100
366 ms32812 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=1e9+7;
struct upd { long long l,r,v; };
struct query { long long l,r,lc,x,y; };
struct fenwicktree
{
	long long fen[MAXN];
	void update(int i,int n,long long val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
	long long get(int i) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
};
bool comp(upd a,upd b) { return a.v<b.v; }
vector<int> ds[MAXN];
pair<int,int> edge[MAXN];
int L[MAXN],R[MAXN],ans[MAXN],sp[MAXN][20],dis[MAXN],cnt[MAXN],tdfs=0;
fenwicktree fa,fb;
upd U[MAXN];
query Q[MAXN];
void dfs(int i,int pre)
{
	L[i]=++tdfs,sp[i][0]=pre;
	for(int j=1;j<=17;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
	R[i]=tdfs;
}
void dfs2(int i,int pre)
{
	for(auto v:ds[i]) if(v!=pre)
	{
		cnt[v]+=cnt[i];
		dfs2(v,i);
	}
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=17;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=17;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
void solve(int l,int r,int n,vector<int> vq)
{
	if(l==r)
	{
		for(auto v:vq) ans[v]=cnt[Q[v].l]+cnt[Q[v].r]-cnt[Q[v].lc]*2-(fb.get(L[Q[v].l])+fb.get(L[Q[v].r])-fb.get(L[Q[v].lc])*2);
		return ;
	}
	int mid=(l+r)/2;
	for(int i=l;i<=mid;i++)
	{
		fa.update(U[i].l,n,U[i].v),fa.update(U[i].r+1,n,-U[i].v);
		fb.update(U[i].l,n,1),fb.update(U[i].r+1,n,-1);
	}
	vector<int> vl,vr;
	for(auto v:vq) if(fa.get(L[Q[v].l])+fa.get(L[Q[v].r])-fa.get(L[Q[v].lc])*2<=Q[v].y) vr.push_back(v);
	else vl.push_back(v);
	solve(mid+1,r,n,vr);
	for(int i=mid;i>=l;i--)
	{
		fa.update(U[i].l,n,-U[i].v),fa.update(U[i].r+1,n,U[i].v);
		fb.update(U[i].l,n,-1),fb.update(U[i].r+1,n,1);
	}
	solve(l,mid,n,vl);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	edge[i]={l,r},ds[l].push_back(r),ds[r].push_back(l);
	}
	dfs(1,1);
	for(int i=1;i<=m;i++)
	{
		int p,c;
		cin>>p>>c;
		int l=edge[p].first,r=edge[p].second;
		if(dis[l]<dis[r]) swap(l,r);
		U[i]={L[l],R[l],c},cnt[l]++;
	}
	dfs2(1,1);
	U[++m]={1,0,INF};
	sort(U+1,U+m+1,comp);
	vector<int> vq;
	for(int i=1;i<=q;i++)
	{
		long long s,t,x,y;
		cin>>s>>t>>x>>y;
		int lc=lca(s,t);
		Q[i]={s,t,lc,x,y},vq.push_back(i);
	}
	solve(1,m,n,vq);
	for(int i=1;i<=q;i++) cout<<max(-1LL,Q[i].x-ans[i])<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...