题解：P14436 [JOISC 2013] 间谍 / Spy

闲话

大手子很早就过了，但是我没有，所以被嘲讽了。

正文

形式化题意

题目又臭又长，简化一下。

给你两棵有根树

Tree_{j}

和

Tree_{i}

，都有

N

个节点，但是可能不同构，两棵树间点的对应关系是

i_{1}

对

j_{1}

，

i_{2}

对

j_{2}

，以此类推，就是一一对应。

现在给你

M

次操作，每次操作将给你两个点

R_{j}

和

S_{i}

，每次求多少个

Tree_{i}

上的点满足：

在 $Tree_{j}$ 上对应点属于 $R_{j}$ 的子树。
在 $Tree_{i}$ 上属于 $S_{i}$ 的子树。

最后问你，

Tree_{i}

上的每个点共满足多少次。

思路

一般来说，对于树上问题，凡是有关子树的，都可以想到用 DFS 序来解决，所以接下来我们定义：

$dfn1_{i}$ 表示点 $i$ 在 $Tree_{i}$ 上的 DFS 序， $dfn2_{j}$ 表示点 $j$ 在 $Tree_{j}$ 上的 DFS 序。
$siz1_{i}$ 表示点 $i$ 在 $Tree_{i}$ 上的子树大小， $siz2_{j}$ 表示点 $j$ 在 $Tree_{j}$ 上的子树大小。

根据 DFS 序的优良性质，我们可以发现对于每次操作，满足条件的点

i

都可以转化成下面的条件：

$dfn1_{R}\le dfn1_{i}\le dfn1_{R}+siz1_{R}-1$
$dfn2_{S}\le dfn2_{i}\le dfn2_{S}+siz2_{S}-1$

这长得很像二维偏序，所以我们考虑把问题放到二维平面上来。

定义点

i

在二维平面上的对应坐标为

(dfn1_{i},dfn2_{i})

，则我们可以发现每次操作等价于在二维平面上将点

R

和

S

之间的矩形贡献全部加一，就是区间修改。而每次的查询就是问点

i

即

(dfn1_{i},dfn2_{i})

在二维平面上被计算了几次。

这明显是二维差分，不过我用的是二维树状数组~~因为有人用了差分~~，时间为

\Theta(m\times \log ^{2}n+n\times \log ^{2}n)

，可以通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
struct BIT2{//二维差分树状数组 
	int n;V<V<int> >t;
	BIT2(int _n):n(_n+2),t(_n+3,V<int>(_n+3)){}
	#define lb(x) ((x)&(-x))
	void add(int x,int y,int w){
		for(int i=x;i<=n;i+=lb(i)){
			for(int j=y;j<=n;j+=lb(j)) t[i][j]+=w;
		}
	}
	void update(int a,int b,int x,int y,int w){//(a,b)到(x,y)（左上到右下）整体加w 
		add(a,b,w);
		add(a,y+1,-w);
		add(x+1,b,-w);
		add(x+1,y+1,w);
	}
	int query(int x,int y){//单点查询 
		int ans=0;
		for(int i=x;i;i-=lb(i)){
			for(int j=y;j;j-=lb(j)) ans+=t[i][j];
		}
		return ans;
	}
	#undef lb
};
int num=0;
void dfs(int u,int fa,V<V<int> >&e,V<int>&dfn,V<int>&siz){
	dfn[u]=++num;
	siz[u]=1;
	for(int v:e[u]){
		if(v==fa)continue;
		dfs(v,u,e,dfn,siz);
		siz[u]+=siz[v];
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	BIT2 lls(n);
	V<V<int> >e1(n+1),e2(n+1);
	int root1=-1,root2=-1;
	FOR(i,1,n){
		int fa1,fa2;cin>>fa1>>fa2;
		if(fa1==0) root1=i;
		else e1[fa1].pb(i),e1[i].pb(fa1);
		if(fa2==0) root2=i;
		else e2[fa2].pb(i),e2[i].pb(fa2);
	}
	V<int>dfn1(n+1),dfn2(n+1),siz1(n+1),siz2(n+1);
	dfs(root1,0,e1,dfn1,siz1);num=0;
	dfs(root2,0,e2,dfn2,siz2);
	FOR(i,1,m){
		int r,s;cin>>r>>s;
		lls.update(dfn1[r],dfn2[s],dfn1[r]+siz1[r]-1,dfn2[s]+siz2[s]-1,1);
	}
	FOR(i,1,n){
		cout<<lls.query(dfn1[i],dfn2[i])<<"\n";
	}
	return 0;
}

题解：P14436 [JOISC 2013] 间谍 / Spy

文章操作

闲话

正文

形式化题意

思路

代码

相关推荐

评论

题解：P14436 [JOISC 2013] 间谍 / Spy