专栏文章

P9340 [JOISC 2023] Tourism (Day3) 题解

P9340题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipbi1mz
此快照首次捕获于
2025/12/03 09:17
3 个月前
此快照最后确认于
2025/12/03 09:17
3 个月前
查看原文

前置知识

解法

考虑对 aia_{i} 扫描线后柯朵莉树在链上进行区间覆盖,然后转化为查询颜色 [l,r]\in [l,r] 内的点的个数,可以使用树状数组维护。
当然,也可以无脑直接覆盖到根节点,然后对区间 LCA\operatorname{LCA} 的根链进行容斥,求一遍区间内 DFS 序最小和最大的两个点的 LCA\operatorname{LCA} 即可。
代码中写的是对 (ai1,ai)(a_{i-1},a_{i}) 这条链进行覆盖的写法。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
struct node
{
	int nxt,to;
}e[200010];
int head[200010],fa[200010],siz[200010],dep[200010],son[200010],top[200010],dfn[200010],ans[200010],a[200010],tot=0,cnt=0;
vector<pair<int,int> >q[200010];
void add(int u,int v)
{
	cnt++;  e[cnt]=(node){head[u],v};  head[u]=cnt;
}
void dfs1(int x,int father)
{
	siz[x]=1;
	fa[x]=father;
	dep[x]=dep[father]+1;
	for(int i=head[x];i!=0;i=e[i].nxt)  if(e[i].to!=father)
	{
		dfs1(e[i].to,x);
		siz[x]+=siz[e[i].to];
		son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
	}
}
void dfs2(int x,int id)
{
	top[x]=id;
	tot++;  dfn[x]=tot;
	if(son[x]!=0)
	{
		dfs2(son[x],id);
		for(int i=head[x];i!=0;i=e[i].nxt)  
		{
			if(e[i].to!=fa[x]&&e[i].to!=son[x])  dfs2(e[i].to,e[i].to);
		}	
	}
}
struct BIT
{
	int c[200010];
	int lowbit(int x)
	{
		return (x&(-x));
	}
	void add(int n,int x,int val)
	{
		if(x==0)  return;
		for(int i=x;i<=n;i+=lowbit(i))  c[i]+=val;
	}
	int getsum(int x)
	{
		int ans=0;
		for(int i=x;i>=1;i-=lowbit(i))  ans+=c[i];
		return ans;
	}
}T;
struct ODT
{
	struct node
	{
		int l,r;
		mutable int col;
		bool operator < (const node &another) const
		{
			return l<another.l;
		}
	};
	set<node>s;
	void init(int n)
	{
		s.insert((node){1,n,0});
	}
	set<node>::iterator split(int pos)
	{
		set<node>::iterator it=s.lower_bound((node){pos,0,0});
		if(it!=s.end()&&it->l==pos)  return it;
		it--;
		if(it->r<pos)  return s.end();
		int l=it->l,r=it->r,col=it->col;
		s.erase(it);
		s.insert((node){l,pos-1,col});
		return s.insert((node){pos,r,col}).first;
	}
	void assign(int l,int r,int col,int n)
	{
		set<node>::iterator itr=split(r+1),itl=split(l);
		for(set<node>::iterator it=itl;it!=itr;it++)  T.add(n,it->col,-(it->r-it->l+1));
		T.add(n,col,r-l+1);
		s.erase(itl,itr);
		s.insert((node){l,r,col});
	}
}O;
void update(int u,int v,int col,int n)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]])
		{
			O.assign(dfn[top[u]],dfn[u],col,n);
			u=fa[top[u]];
		}
		else
		{
			O.assign(dfn[top[v]],dfn[v],col,n);
			v=fa[top[v]];
		}
	}
	if(dep[u]<dep[v])  O.assign(dfn[u],dfn[v],col,n);
	else  O.assign(dfn[v],dfn[u],col,n);
}
int main()
{
// #define Isaac
#ifdef Isaac
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n,m,k,u,v,i,j;
	cin>>n>>m>>k;
	for(i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		add(u,v);  add(v,u);
	}
	for(i=1;i<=m;i++)  cin>>a[i];
	for(i=1;i<=k;i++)
	{
		cin>>u>>v;
		if(u==v)  ans[i]=1;
		else  q[v].push_back(make_pair(u,i));
	}
	dfs1(1,0);  dfs2(1,1);  O.init(n);
	for(i=2;i<=m;i++)
	{
		update(a[i-1],a[i],i,m);
		for(j=0;j<q[i].size();j++)  ans[q[i][j].second]=T.getsum(i)-T.getsum(q[i][j].first);
	}
	for(i=1;i<=k;i++)   cout<<ans[i]<<endl;
	return 0;
}

评论

1 条评论,欢迎与作者交流。

正在加载评论...