题意

给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。

n＝40000，m＝100000
Sol

树上莫队模板题
# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

const int _(1e5 + 5);

typedef long long ll;

IL int Input(){

    RG int x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int n, m, first[_], cnt, w[_], o[_], len;

int dfn[_], st[20][_], lg[_], deep[_], idx, fa[_];

int S[_], bl[_], blo, num, ans[_], sum[_], vis[_], Ans;

struct Edge{

	int to, next;

} edge[_];

struct Query{

	int l, r, id;

	IL int operator <(RG Query B) const{

		return bl[l] == bl[B.l] ? dfn[r] < dfn[B.r] : bl[l] < bl[B.l];

	}

} qry[_];

IL void Add(RG int u, RG int v){

	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;

}

IL void Dfs(RG int u){

	dfn[u] = ++idx, st[0][idx] = u; RG int l = S[0];

	for(RG int e = first[u]; e != -1; e = edge[e].next){

		RG int v = edge[e].to;

		if(dfn[v]) continue;

		deep[v] = deep[u] + 1, fa[v] = u;

		Dfs(v);

		if(S[0] - l >= blo) for(++num; S[0] != l; --S[0]) bl[S[S[0]]] = num;

		st[0][++idx] = u;

	}

	S[++S[0]] = u;

}

IL void Chk(RG int &x, RG int u, RG int v){

	x = deep[u] < deep[v] ? u : v;

}

IL int LCA(RG int u, RG int v){

	u = dfn[u], v = dfn[v];

	if(u > v) swap(u, v);

	RG int log2 = lg[v - u + 1], t;

	Chk(t, st[log2][u], st[log2][v - (1 << log2) + 1]);

	return t;

}

IL void Update(RG int x){

	if(vis[x]) --sum[w[x]], Ans -= (!sum[w[x]]);

	else Ans += (!sum[w[x]]), ++sum[w[x]];

	vis[x] ^= 1;

}

IL void Modify(RG int u, RG int v){

	while(u != v){

		if(deep[u] > deep[v]) swap(u, v);

		Update(v), v = fa[v];

	}

}

int main(RG int argc, RG char* argv[]){

	len = n = Input(), m = Input(), blo = sqrt(n);

	for(RG int i = 1; i <= n; ++i) o[i] = w[i] = Input(), first[i] = -1;

	sort(o + 1, o + len + 1), len = unique(o + 1, o + len + 1) - o - 1;

	for(RG int i = 1; i <= n; ++i) w[i] = lower_bound(o + 1, o + len + 1, w[i]) - o;

	for(RG int i = 1, u, v; i < n; ++i)

		u = Input(), v = Input(), Add(u, v), Add(v, u);

	Dfs(1);

	if(S[0]) for(++num; S[0]; --S[0]) bl[S[S[0]]] = num;

	for(RG int i = 2; i <= idx; ++i) lg[i] = lg[i >> 1] + 1;

	for(RG int j = 1; j <= lg[idx]; ++j)

		for(RG int i = 1; i + (1 << j) - 1 <= idx; ++i)

			Chk(st[j][i], st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

	for(RG int i = 1; i <= m; ++i){

		qry[i] = (Query){Input(), Input(), i};

		if(dfn[qry[i].l] > dfn[qry[i].r]) swap(qry[i].l, qry[i].r);

	}

	sort(qry + 1, qry + m + 1);

	RG int lca = LCA(qry[1].l, qry[1].r);

	Modify(qry[1].l, qry[1].r);

	Update(lca), ans[qry[1].id] = Ans, Update(lca);

	for(RG int i = 2; i <= m; ++i){

		Modify(qry[i - 1].l, qry[i].l), Modify(qry[i - 1].r, qry[i].r);

		lca = LCA(qry[i].l, qry[i].r);

		Update(lca), ans[qry[i].id] = Ans, Update(lca);

	}

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

    return 0;

}
巴特西

SPOJ：COT2 Count on a tree II

题意

Sol

最新文章

热门文章
