CF1110F Nearest Leaf

传送门

这是我第二次看见这个题目了，第一次看见是另一场比赛的A题，想了一个小时不会写就弃了

从来没想过这个题能这么玩

线段树上记录根到叶子节点的距离

初始线段树上先记下根节点1到各叶子节点的距离

先离线，然后dfs整颗树，在dfs过程中考虑根的移动对线段树的影响

如果当前点是查询点，在当前线段树上查询

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

void read(int &x) {

	char ch; bool ok;

	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

#define rg register

const int maxn=5e5+10;

const long long inf=1e15;

int n,m,cnt,mx[maxn],v[maxn*2],pre[maxn*2],nxt[maxn*2],h[maxn],x[maxn],y[maxn],now=1;

struct oo{int l,r;long long mx,la;}s[maxn*4];

struct o{int v,l,r,id;}a[maxn];

long long ans[maxn];

void add(int x,int y,int z)

{

	pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt,v[cnt]=z;

	pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt,v[cnt]=z;

}

void update(int x){s[x].mx=min(s[x<<1].mx,s[x<<1|1].mx);}

void build(int x,int l,int r)

{

	s[x].l=l,s[x].r=r;

	if(l==r){s[x].mx=inf;return ;}

	int mid=(l+r)>>1;

	build(x<<1,l,mid),build(x<<1|1,mid+1,r);

	update(x);

}

void pushdown(int x)

{

	int ls=x<<1,rs=x<<1|1;

	s[ls].mx+=s[x].la,s[rs].mx+=s[x].la;

	s[ls].la+=s[x].la,s[rs].la+=s[x].la;

	s[x].la=0;

}

void change(int x,int l,int r,long long v,int id)

{

	if(l<=s[x].l&&r>=s[x].r){id?s[x].mx=v:s[x].mx+=v;s[x].la+=v;return ;}

	if(s[x].la)pushdown(x);

	int mid=(s[x].l+s[x].r)>>1;

	if(l<=mid)change(x<<1,l,r,v,id);

	if(r>mid)change(x<<1|1,l,r,v,id);

	update(x);

}

void dfs(int x,int fa,long long dep)

{

	mx[x]=x;

	for(rg int i=h[x];i;i=nxt[i])

		if(pre[i]!=fa)dfs(pre[i],x,dep+v[i]),mx[x]=max(mx[x],mx[pre[i]]);

	if(mx[x]==x)change(1,x,x,dep,1);

}

bool cmp(o a,o b){return a.v<b.v;}

long long get(int x,int l,int r)

{

	if(l<=s[x].l&&r>=s[x].r)return s[x].mx;

	if(s[x].la)pushdown(x);

	int mid=(s[x].l+s[x].r)>>1;long long ans=inf;

	if(l<=mid)ans=min(ans,get(x<<1,l,r));

	if(r>mid)ans=min(ans,get(x<<1|1,l,r));

	update(x);return ans;

}

void dfs1(int x,int fa)

{

	while(a[now].v==x)ans[a[now].id]=get(1,a[now].l,a[now].r),now++;

	for(rg int i=h[x];i;i=nxt[i])

		if(pre[i]!=fa)

		{

			change(1,1,n,v[i],0),change(1,pre[i],mx[pre[i]],-2*v[i],0);

			dfs1(pre[i],x);

			change(1,1,n,-v[i],0),change(1,pre[i],mx[pre[i]],2*v[i],0);

		}

}

signed main()

{

	read(n),read(m),build(1,1,n);

	for(rg int i=2;i<=n;i++)read(x[i]),read(y[i]);

	for(rg int i=n;i>=2;i--)add(i,x[i],y[i]);

	dfs(1,0,0);

	for(rg int i=1;i<=m;i++)read(a[i].v),read(a[i].l),read(a[i].r),a[i].id=i;

	sort(a+1,a+m+1,cmp);

	dfs1(1,0);

	for(rg int i=1;i<=m;i++)printf("%lld\n",ans[i]);

}

巴特西

CF1110F Nearest Leaf

传送门

最新文章

热门文章