BZOJ 4539 树

发表于 | 更新于

Link

真的是很不错的题目..

Solution

借鉴虚树和树分块的思想，尽量减少新树的点数，把一块看成一个整体，在新树中只记录一块的根节点。 需要把一个子树连到大树的点pp上，用二分查找找到pp所在的块，然后用主席树算出pp在原树对应的节点编号。 查询的时候，求出两个点所在块的 ，让这两个点分别跳到处于 块里面的最深的祖先(自身也算)并记录路径长度，再在块内求一个 ，算一下路径长度就好了。

Tips

有一个构造函数的一个int64变量写成了int，怎么也搞不出来。 对拍的时候，确实造了每次+n+n的极限数据，但是查询是随机的，所以没有让这个问题暴露出来。 so，极限数据要在每个方面都极限。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include "lucida"
using std::lower_bound;
using std::swap;
const int MAXN=100000+11,MAXLOG=20;
int n,log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i)
		log_2[i]=log_2[i>>1]+1;
}}Auto;
struct Edge {
	int to;int64 v;Edge *pre;
	Edge(int to,int64 v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<2);
		return Me++;
	}
};
namespace segtree {
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node():cnt(0) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN*MAXLOG);
			return Me++;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
	}*_null=null=new Node,*_null_son=null->son[0]=null->son[1]=null;
	struct SegTree {
		Node **root;int L,R;
		void Build(Node *&pos,int L,int R,int goal) {
			pos=new Node(*pos);
			if(L==R) pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Build(pos->son[0],L,Mid,goal);
				else Build(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
		int Kiss(Node *pl,Node *pr,int L,int R,int K) {
			if(L==R) return L;
			else {
				int Mid=(L+R)>>1,sz=pr->son[0]->cnt-pl->son[0]->cnt;
				return K<=sz?Kiss(pl->son[0],pr->son[0],L,Mid,K):Kiss(pl->son[1],pr->son[1],Mid+1,R,K-sz);
			}
		}
		SegTree(){}SegTree(int a[],int n):root(alloc(Node*,n+1)),L(1),R(n) {
			root[0]=null;
			for(int i=1;i<=n;++i)
				Build(root[i]=root[i-1],L,R,a[i]);
		}
		int Kiss(int l,int r,int K) {
			return Kiss(root[l-1],root[r],L,R,K);
		}
	};
}using segtree::SegTree;
struct Graph {
	Edge *G[MAXN];
	Graph() {
		dep[1]=1;
	}
	void Adde(const int &f,const int &t,const int64 &v) {
		G[f]=new Edge(t,v,G[f]);
		G[t]=new Edge(f,v,G[t]);
	}
	void operator () (const int &f,const int &t,const int64 &v) {
		Adde(f,t,v);
	}
	Edge *operator [](const int &x) {
		return G[x];
	}
	int par[MAXN][MAXLOG],fa[MAXN],sz[MAXN],dep[MAXN],dfs[MAXN],lbd[MAXN],rbd[MAXN],dc;
	int64 len[MAXN];//dep深度 len距离
	int LCA(int p1,int p2) {
		if(dep[p1]<dep[p2]) swap(p1,p2);
		for(int lg=log_2[dep[p1]-dep[p2]];~lg;--lg)
			p1=dep[par[p1][lg]]>=dep[p2]?par[p1][lg]:p1;
		if(p1==p2) return p1;
		for(int lg=log_2[dep[p1]];~lg;--lg)
			if(par[p1][lg]!=par[p2][lg])
				p1=par[p1][lg],p2=par[p2][lg];
		assert(fa[p1]);
		return fa[p1];
	}
	void DFS(int pos=1) {
		par[pos][0]=fa[pos];
		for(int lg=1;lg<=log_2[dep[pos]];++lg)
			par[pos][lg]=par[par[pos][lg-1]][lg-1];
		dfs[++dc]=pos;
		lbd[pos]=dc;
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa[pos]) {
				int u=e->to;
				fa[u]=pos;
				dep[u]=dep[pos]+1;
				len[u]=len[pos]+e->v;
				DFS(u);
				sz[pos]+=sz[u];
			}
		rbd[pos]=dc;
	}
	int64 Len(int bot,int top) {
		return len[bot]-len[top];
	}
};
struct OriginGraph : Graph{
	SegTree seg;
	void Build() {
		DFS(1);
		new(&seg) SegTree(dfs,dc);
	}
	int KthNode(int rt,int K) {
		return seg.Kiss(lbd[rt],rbd[rt],K);
	}
	int Dist(int p1,int p2) {
		int lca=LCA(p1,p2);
		return len[p1]+len[p2]-len[lca]*2;
	}
}oi;
struct NewGraph : Graph{
	struct Block {
		int64 last,rFa;int vRt;
		Block(){}
		Block(const int64 &last,const int64 &rFa,const int &vRt):last(last),rFa(rFa),vRt(vRt) {} //int rFa??
		bool operator <(const Block &a) const {
			return last<a.last;
		}
	}np[MAXN];int nc;
	struct Point {//Point Info
		int bNum,vRef;
		//block Number
		//virtual Reference in original Tree
		Point(const int &bNum,const int &vRef):bNum(bNum),vRef(vRef) {}
	};
	void Set(const int &n) {
		np[nc=1]=Block(n,0,1);
	}
	Point Ident(const int64 &pos) {
		int bNum=lower_bound(np+1,np+1+nc,Block(pos,0,0))-np,
			vRef=oi.KthNode(np[bNum].vRt,pos-np[bNum-1].last);
		return Point(bNum,vRef);
	}
	void Join(int rt,int64 goal) {
		++nc;np[nc]=Block(np[nc-1].last+oi.sz[rt],goal,rt);
		Point go=Ident(goal);
		Adde(nc,go.bNum,oi.Len(go.vRef,np[go.bNum].vRt)+1);
	}
	int64 JumpTo(int64 &pos,Point &pi,int bgo) {//跳到它上面的bgo块中的最深节点，并计算距离
		if(pi.bNum==bgo)
			return 0;
		else {
			int64 res=oi.Len(pi.vRef,np[pi.bNum].vRt);int b=pi.bNum;
			for(int lg=log_2[dep[b]];~lg;--lg)
				if(dep[par[b][lg]]>dep[bgo]) {
					b=par[b][lg];
				}
			res+=Len(pi.bNum,b)+1;
			pos=np[b].rFa;pi=Ident(pos);
			return res;
		}
	}
	int64 Dist(int64 p1,int64 p2) {
		Point t1=Ident(p1),t2=Ident(p2);
		int blca=LCA(t1.bNum,t2.bNum);
		int64 res=JumpTo(p1,t1,blca)+JumpTo(p2,t2,blca);
		res+=oi.Dist(t1.vRef,t2.vRef);
		return res;
	}
}nw;

int main() {
	freopen("input","r",stdin);
	int m,Q;is>>n>>m>>Q;
	for(int i=1;i<=n-1;++i) {
		int f,t;is>>f>>t;
		oi(f,t,1);
	}
	oi.Build();nw.Set(n);
	for(int i=1;i<=m;++i) {
		int x;int64 to;is>>x>>to;
		nw.Join(x,to);
	}
	nw.DFS();
	for(int i=1;i<=Q;++i) {
		int64 x,y;is>>x>>y;
		int64 Ans=nw.Dist(x,y);
		os<<Ans<<'\n';
	}
	return 0;
}