萌新点分治WA #6求助
查看原帖
萌新点分治WA #6求助
487397
Lagrange_i_f楼主2024/6/16 11:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int head[N],vct[N],nxt[N],edge[N],idx;
void add(int x,int y,int w){
	vct[++idx]=y;edge[idx]=w;
	nxt[idx]=head[x];head[x]=idx;
}
//adde()
int siz[N],dp[N],s1,res;
bool vis[N];
void work1(int u,int f){
	dp[u]=0;
	for(int i=head[u];i;i=nxt[i]){
		int v=vct[i];
		if(v==f||vis[v])continue;
		work1(v,u);
		dp[u]=max(dp[u],siz[v]);
	}
	dp[u]=max(dp[u],s1-siz[u]);
	if(dp[u]<=s1/2)res=u;
}
void get(int u,int f){
	siz[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=vct[i];
		if(v==f||vis[v])continue;
		get(v,u);
		siz[u]+=siz[v];
	}
}
int n,l,w;
int dep[N],depw[N],cnt,tot;
pair<int,int>h1[N],h[N];
void ad(int u,int f){
	for(int i=head[u];i;i=nxt[i]){
		int v=vct[i];
		if(vis[v]||v==f)continue;
		dep[v]=dep[u]+1; depw[v]=depw[u]+edge[i];
		ad(v,u);
	}
	h1[++tot]=h[++cnt]=make_pair(depw[u],dep[u]);
}
struct Bitts{
	int c[N];
	int lowbit(int l){
		return l&(-l);
	}
	void update(int pos,int k){
		pos++;
		if(pos<=0)return ;
		for(int i=pos;i<N;i+=lowbit(i))c[i]+=k;
	}
	int query(int pos){
		int res=0;
		pos++;
		if(pos<=0)return 0;
		for(int i=pos;i;i-=lowbit(i))res+=c[i];
		return res;
	}
}st;
int ans=0;
int calc(){
//	cout<<tot<<' ';
	int sum=0;
	sort(h1+1,h1+1+tot);
	for(int i=1;i<=tot;i++)st.update(h1[i].second,1);
	int i=1,j=tot;
	while(i<j){
		if(h1[i].first+h1[j].first<=w){
			st.update(h1[i].second,-1);
			sum+=st.query(l-h1[i].second); 
			i++;
		}else{
			st.update(h1[j].second,-1);
			j--;
		}
	}
	st.update(h1[i].second,-1);
//	while(j>=i)st.update(h1[j--].second,-1);
	return sum;
}
int gans(){
	int sum=0;
	sort(h+1,h+1+cnt);
	for(int i=1;i<=cnt;i++)st.update(h[i].second,1);
	int i=1,j=cnt;
	while(i<j){
		if(h[i].first+h[j].first<=w){
			st.update(h[i].second,-1);
			sum+=st.query(l-h[i].second); 
			i++;
		}else{
			st.update(h[j].second,-1);
			j--;
		}
	}
	st.update(h[i].second,-1);
//	while(j>=i)st.update(h[j--].second,-1);
	return sum;
}
void solve(int u){
	get(u,0);
	s1=siz[u];
	work1(u,0);
//	cout<<res<<' ';
	vis[res]=1;
	dep[res]=depw[res]=0;
	cnt=0;
	h[++cnt]=make_pair(0,0);
//	cout<<1;
	for(int i=head[res];i;i=nxt[i]){
		int v=vct[i];
		if(vis[v])continue;
		dep[v]=1,depw[v]=edge[i];
//		cout<<depw[v]<<'&';		
		tot=0;
		ad(v,u);
		ans-=calc();
//		cout<<k<<'*'<<v<<' ';
//		k-=
	}
	ans+=gans();
//	cout<<k<<' '<<u<<'\n';
	for(int i=head[res];i;i=nxt[i]){
		int v=vct[i];
		if(vis[v])continue;
		solve(v);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>l>>w;
	for(int i=1;i<n;i++){
		int p,z;
		cin>>p>>z;
		add(i+1,p,z),add(p,i+1,z);
	} 
	solve(1);
	cout<<ans;
	return 0;
}
2024/6/16 11:46
加载中...