专栏文章
P9340 [JOISC 2023] Tourism (Day3) 题解
P9340题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mipbi1mz
- 此快照首次捕获于
- 2025/12/03 09:17 3 个月前
- 此快照最后确认于
- 2025/12/03 09:17 3 个月前
前置知识
解法
考虑对 扫描线后柯朵莉树在链上进行区间覆盖,然后转化为查询颜色 内的点的个数,可以使用树状数组维护。
当然,也可以无脑直接覆盖到根节点,然后对区间 的根链进行容斥,求一遍区间内 DFS 序最小和最大的两个点的 即可。
代码中写的是对 这条链进行覆盖的写法。
代码
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 条评论,欢迎与作者交流。
正在加载评论...