CF1527D MEX Tree

MEX Tree – Luogu | New Ecosystem of Computer Science Education (luogu.com.cn)

Article directory

CF1527D MEX Tree
- The general idea of the topic
- The basic idea
- ask
- Revise
- code

The main idea of the title

give one

A tree of n points, starting from

0 to

n-1

n?1 number. The weight that defines a path is the number of all points on the path

mex

mex. for each

≤

0\le i\le n

0≤i≤n find

mex

mex for

There are several paths to i. Note that the paths counted here need to include at least one edge.

a collection of

mex

mex is defined as the smallest non-negative integer not in the set.

Basic idea

It is observed that we are dealing with

When i,

→

0\to i – 1

0→i?1 must be on a path, otherwise all subsequent answers will be

s

z

i

sz_i

szi? means

i

i

i is the size of the subtree of the root

s

p

sp

sp means not

0

0

0 endpoint is located for

0

0

The corresponding subtree size of 0

The doubling requirement will be used below

lca

We can do something similar to virtual tree operation.

Here it is assumed that

0

0

0 is the root

Ask

So the query can be divided into

3 situations:

i

i

i is in the current path
i

i

i is a descendant of the current path endpoint
i

i

i does not belong to the above situation

Then

mex = 0

mex=0 and

mex = 1

mex=1 is a special treatment

when

mex = 0

When mex=0:

As long as you don’t pass by

0 paths all meet the conditions

So the answer is

Select any path between two points in all subtrees of 0

when

mex = 1

When mex=1:

exist

Number of options for selecting any two points among n points

–

mex = 0

Number of solutions with mex=0

LL gs (LL x) {<!-- --> return x * (x - 1) / 2; }
void pre_ans () {<!-- -->
    ans[1] = gs (sz[0] - sz[1]);
    int y;
    for (int i = hd[0] ; i ; i = e[i].nt) {<!-- -->
        y = e[i].to;
        ans[0] + = gs (sz[y]);
        int lca = Lca (y , 1);
        if (lca == y) ans[1] -= gs (sz[y] - sz[1]);
        else ans[1] -= gs (sz[y]);
    }
}

Now we divide other inquiries into two situations

Neither endpoint nor

0

0

0, the two endpoints are

x

,

y

x , y

x, y

i

i

i on the path $lca(x , i) =i \or lca (y , i) = i $

The answer is

0

0

0
i

i

i is a descendant of the current path endpoint KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) = x \?o?r? ?lca (y , i) = y

The answer is that for the endpoint subtree size

?

–

?

s

z

i

sz_i

szi? multiplied by the other terminal tree size
Otherwise, the answer is

s

z

x

?

s

z

y

sz_x*sz_y

szxszy?

There is a point for

0

0

In the case of 0, the other endpoint is

x

x

i

i

i is in the current path

l

c

a

(

x

,

i

)

=

i

lca (x , i) = i

lca(x,i)=i

The answer is

0

0

0
i

i

i is a descendant of the current path endpoint

i

i

i is a descendant of the endpoint that is not zero

l

c

a

(

x

,

i

)

=

x

lca (x , i) = x

lca(x,i)=x, then the answer is:

(

s

i

z

[

x

]

?

s

i

z

[

i

]

)

?

(

s

i

z

[

0

]

?

s

p

)

(siz[x] – siz[i]) * (siz[0] – sp)

(siz[x]?siz[i])?(siz[0]?sp)

i

i

i is

0

0

0 descendants

l

c

a

(

x

,

i

)

=

0

lca (x , i) = 0

lca(x,i)=0, then the answer is:

(

s

i

z

[

0

]

?

s

p

?

s

i

z

[

i

]

)

?

s

i

z

[

x

]

(siz[0] – sp – siz[i]) * siz[x]

(siz[0]?sp?siz[i])?siz[x]
i

i

i does not belong to any of the above situations

So

i

i

i is the fork of the current path, then the answer is:

(

s

i

z

[

0

]

?

s

p

)

?

s

i

z

[

x

]

(siz[0] – sp) * siz[x]

(siz[0]?sp)?siz[x]

LL gt_ans (int x) {<!-- -->
    int lca1 = Lca (x , l) , lca2 = Lca (x , r);
    LL ans1, ans2;
    if (r) {<!-- -->
        ans1 = sz[l] , ans2 = sz[r];
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca2 == r) ans2 -= sz[x];
    }
    else {<!-- -->
        ans1 = sz[l] , ans2 = sz[r] - sp;
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca1 == 0) ans2 -= sz[x];
    }
    return ans1 * ans2;
}

Modify

try to

i is added to the current path

1. Neither of the two ends

i

i

i is already on the path KaTeX parse error: Undefined control sequence: \or at position 17: …ca (x , i) = i \?o?r? ?lca (y , i) = i

Don’t worry about it
i

i

i is a descendant of one end $lca(x, i) = x \or lca (y, i) = y $

Just set that endpoint to

i

i

i would be fine
If it does not fall into the above two situations

Then it is a bifurcation, and the answers directly below are all

0

0

0 would be fine

2. At least one end is

0 case

If both ends are

0

0

0

Directly set one end to

i

i

i
i

i

i is already on the path

l

c

a

(

x

,

i

)

=

i

lca (x , i) = i

lca(x,i)=i

Never mind
l

c

a

(

x

,

i

)

=

x

lca (x , i) = x

lca(x,i)=x

x

=

i

x = i

x=i
Does not belong to the above situation

1. bifurcation

l

c

a

(

x

,

i

)

≠

0

lca (x , i)\
eq 0

lca(x,i)=0 insertion failed

2,

x

≠

0

x \
eq 0

x=0 and

l

c

a

(

x

,

i

)

=

0

lca (x , i) = 0

lca(x,i)=0, then

y

=

i

y = i

y=i

bool add (int x) {<!-- -->
    int lca1 = Lca (l , x) , lca2 = Lca (r , x);
    if (r) {<!-- -->
        if (lca1 == l) {<!-- -->
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        if (lca2 == r) {<!-- -->
            r = x;
            return 1;
        }
        else if (lca2 == x) return 1;
    }
    else {<!-- -->
        if (lca1 & amp; & amp; (lca1 != l & amp; & amp; lca1 != x)) return 0;
        else if (lca1 == l ) {<!-- -->
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        else if (lca1) return 0;
        else {<!-- -->
            r = x;
            return 1;
        }
    }
    return 0;
}

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x + + )
#define fd(x, y, z) for(int x = y; x >= z; x --)
#define LL long long
using namespace std;
const int N = 6e5 + 5 , inf = 2e5;
int n , sz[N] , hd[N] , cnt , fa[N] , sp , dep[N] , f[N << 1][30] , l , r;
LL tw[30] , ans[N] , lg2[inf + 5];
struct E {
    int to, nt;
} e[N << 1];
void add (int x , int y) { e[ + + cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
int Lca (int x , int y) {
    int flg;
    while (dep[x] != dep[y]) {
        flg = 0;
        if (dep[x] > dep[y]) swap (x , y);
        fd (i, 25, 0) {
            while (dep[f[y][i]] > dep[x]) {
                y = f[y][i];
                flg = 1;
            }
        }
        if (!flg) break;
    }
    while (dep[x] != dep[y]) {
        if (dep[x] > dep[y]) swap (x , y);
        y = f[y][0];
    }
    while (x != y) {
        flg = 0;
        fd (i, 25, 0) {
            while (f[x][i] != f[y][i]) {
                x = f[x][i] , y = f[y][i];
                flg = 1;
            }
        }
        if (!flg) break;
    }
    while (x != y)
        x = f[x][0] , y = f[y][0];
    return x;
}
void dfs1 (int x) {
    int y;
    sz[x] = 1;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        y = e[i].to;
        if (fa[x] == y) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y);
        sz[x] + = sz[y];
    }
}
void gt_f () {
    fu (i , 0 , n - 1)
        fu (j , 1 , 25)
            f[i][j] = 0;
    dep[0] = 1;
    dfs1(0);
    fu (i , 0 , n - 1)
        f[i][0] = fa[i];
    fu (j , 1 , 25) {
        fu (i , 0 , n - 1) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
}
LL gs (LL x) {<!-- --> return x * (x - 1) / 2; }
void pre_ans () {<!-- -->
    ans[1] = gs (sz[0] - sz[1]);
    int y;
    for (int i = hd[0] ; i ; i = e[i].nt) {<!-- -->
        y = e[i].to;
        ans[0] + = gs (sz[y]);
        int lca = Lca (y , 1);
        if (lca == y) ans[1] -= gs (sz[y] - sz[1]);
        else ans[1] -= gs (sz[y]);
    }
}
bool add (int x) {<!-- -->
    int lca1 = Lca (l , x) , lca2 = Lca (r , x);
    if (r) {<!-- -->
        if (lca1 == l) {<!-- -->
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        if (lca2 == r) {<!-- -->
            r = x;
            return 1;
        }
        else if (lca2 == x) return 1;
    }
    else {<!-- -->
        if (lca1 & amp; & amp; (lca1 != l & amp; & amp; lca1 != x)) return 0;
        else if (lca1 == l ) {<!-- -->
            l = x;
            return 1;
        }
        else if (lca1 == x) return 1;
        else if (lca1) return 0;
        else {<!-- -->
            r = x;
            return 1;
        }
    }
    return 0;
}
LL gt_ans (int x) {<!-- -->
    int lca1 = Lca (x , l) , lca2 = Lca (x , r);
    LL ans1, ans2;
    if (r) {<!-- -->
        ans1 = sz[l] , ans2 = sz[r];
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca2 == r) ans2 -= sz[x];
    }
    else {<!-- -->
        ans1 = sz[l] , ans2 = sz[r] - sp;
        if (lca1 == x || lca2 == x) return 0;
        else if (lca1 == l) ans1 -= sz[x];
        else if (lca1 == 0) ans2 -= sz[x];
    }
    return ans1 * ans2;
}
int main () {
    tw[0] = 1ll;
    fu (i , 1 , 25) tw[i] = 1ll * tw[i - 1] * 2;
    int T , u , v;
    scanf ("%d" , & amp;T);
    while (T --) {
        scanf ("%d" , & amp;n);
        cnt = 0;
        fu (i , 0 , n) ans[i] = hd[i] = fa[i] = 0;
        fu(i, 0, n)
            fu (j , 0 , 25)
                f[i][j] = -1;
        fu (i , 1 , n - 1) {
            scanf ("%d%d" , & amp;u , & amp;v);
            add (u , v) , add (v , u);
        }
        gt_f ();
        pre_ans ();
        for (int i = hd[0] ; i ; i = e[i].nt) {
            if (Lca (e[i].to , 1) == e[i].to) {
                sp = sz[e[i].to];
                break;
            }
        }
        l = r = 0;
        fu (i , 2 , n) {
            if (!add (i - 1)) break;
            if (i == n) {
                ans[i] = 1;
                break;
            }
            ans[i] = gt_ans (i);
        }
        fu(i, 0, n)
            printf ("%lld " , ans[i]);
        printf ("\
");
    }
    return 0;
}