2020 우 객 다 교 제4 장 A 문제 Ancient Distance dfs 순서 + 선분 수 + k 급 조상

Ancient Distance
제목
N N 개 점 은 점 11 1 을 뿌리 로 하 는 나무 로 나무 에서 K K K 개의 관건 점 을 확정 합 니 다. 각 점 의 가중치 v a l val 을 점 과 점 에서 뿌리 노드 에 부 딪 히 는 첫 번 째 관건 점 의 거리 (경로 에 관건 이 없 으 면 가중치 는 inf * 8289 ° \ inf inf inf) 이 고 답 은 모든 점 에서 최대 가중치 의 최소 값 입 니 다.이제 K = 1, 2,.., N K = 1, 2,..., N K = 1, 2,..., N 의 답 의 합 을 구하 라.
해제
문제 의 뜻 은 이해 하기 어렵 습 니 다. 사례 를 보면 알 수 있 을 것 입 니 다. K K K 값 이 확정 되면 우 리 는 한 번 에 답 을 얻 으 면 트 리 dp 로 해결 할 수 있 을 것 입 니 다. 전체적인 복잡 도 는 O (N 2) O (N ^ 2) O (N2) 입 니 다. 지금 은 반대로 생각 하고 답 이 확 정 된 상황 을 고려 합 니 다.최소 몇 가지 관건 이 필요 합 니까? 점 의 가중치 가 점 과 점 에서 뿌리 노드 에 부 딪 히 는 첫 번 째 관건 점 의 거리 이기 때 문 입 니 다. 사실은 점 과 조상 결점 중의 관건 점 의 깊이 차이 입 니 다. 여기 서 답 을 a n s ans 로 확정 한 후에 우 리 는 나무 중의 깊이 d p > a n s dep > ans dep > ans dep > ans 를 모두 나무 에서 가장 깊 은 점 u u u 를 처리 해 야 합 니 다.u u 에서 계속 위로 a n s ans 개 점 으로 얻 은 a n c e s t o r ancestor ancestor 를 관건 점 으로 설정 합 니 다. 이렇게 v a l [u] = a n s val [u] = ans val [u] = ans 는 왜 a n s ans ans 급 조상 인지 에 대해 서 는 u u u 의 [0, a n s] [0, ans] [0, ans] [0, ans] 급 조상 이면 v a l [u] ≤ a n s val [u] \ \ \ leq ans val [u]≤ ans 는 하나의 관건 적 인 점 인 k e y key key 의 설립 을 고려 하여 k e y key key 의 서브 트 리 에 있 는 모든 점 의 가중치 가 작 아 질 수 있 기 때문에 우 리 는 관건 적 인 영향 을 주 는 점 이 많 을 수록 좋다 (뿌리 와 가 까 울 수록 좋다). 즉, d e p [k e y] dep [key] dep [key] dep [key] 가 작 을 수록 좋다. 그래서 우 리 는 마침 a n s ans ans 급 조상 을 선택 하기 때문에 매번 에 우리 가 k e y key key key 를 확정 한 후에그 하위 트 리 의 점 은 모두 v a l ≤ a n s val \ \ leq ans val ≤ ans 가 있 습 니 다. 우리 가 깊이 가 가장 큰 점 을 계속 찾 으 면 k e y key key 와 그 하위 트 리 의 점 을 더 이상 고려 하지 않 기 때문에 우 리 는 그들 을 덮어 씁 니 다. 즉, 우 리 는 매번 덮어 쓰 지 않 은 점 중 d e p dep dep 의 가장 큰 점 을 찾 을 때마다 이 과정 을 계속 반복 합 니 다.모든 점 이 v a l ≤ a n s val \ \ leq ans val ≤ ans 를 만족 시 킬 때 까지
코드 구현
이 를 통 해 알 수 있 듯 이 우리 가 필요 로 하 는 작업 은 나무의 깊이 가 가장 큰 결점 을 찾 고 한 점 을 덮 는 서브 트 리 를 찾 는 것 이기 때문에 dfs 순서에 따라 선분 트 리 를 만 드 는 것 을 고려 합 니 다.

void dfs(int u, int fa) {
    st[u] = ++dfnt;//dfs       
    for (auto &v: g[u]) if (v != fa) dfs(v, u);
    ed[u] = dfnt;//dfs           
    //  [st, ed]     u    
}

볼 수 있 습 니 다. 우리 가 라인 트 리 에 [s t [u], e d [u] [st [u], ed [u] [st [u], ed [u]] 를 덮 으 면 u u 서브 트 리 의 모든 노드 를 덮 을 수 있 습 니 다. 가장 깊이 있 는 노드 를 조회 하 는 것 은 바로 라인 트 리 의 기본 동작 입 니 다.
또 하나의 조작 이 있 습 니 다. 우 리 는 u u u 의 k - t h k - th k - th 조상 을 찾 아야 합 니 다. 여기 서 배로 처리 할 수 있 습 니 다.

void dfs() {
	//dfs          2^i   
	for (int i = 1; i <= 19; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
}

int kthFa(int u, int k) {//          ,    log(k)
    int bit = 0; 
    while (k) { 
        if (k & 1) u = anc[u][bit]; 
        k >>= 1; 
        bit++;
    } 
    return u; 
}

복잡 도 분석
모든 답 a n s ans ans 에 대해 우 리 는 최대 8968 ° N a n s + 1 * 8969 ° \ lceil \ \ frac {N} {ans + 1} \ rceil * 8968 ° ans + 1 N * 8969 ° 관건 점 을 고려 하면 관건 점 이 서브 트 리 의 모든 점 에 영향 을 줄 수 있 습 니 다. 그러면 우리 의 최 악의 상황 은 서브 트 리 가 체인 입 니 다.영향 을 미 치 는 점 은 a n s + 1 ans + 1 ans + 1 개 밖 에 없 기 때문에 모든 답 은 * 8968 ° N a n s + 1 * 8969 ° \ lceil \ frac {N} {ans + 1} \ rceil * 8968 ° ans + 1 N * 8969 ° 의 관건 점 만 확인 하면 모든 점 에 영향 을 줄 수 있 습 니 다. 우 리 는 한 번 의 조작 으로 선분 나무의 커버 와 조회, 그리고 k 급 조상 을 찾 습 니 다. 이런 조작 은 모두 l o g N logN logN 등급 의 logN 등급 입 니 다.
a n s = 0 , 1 , . . . , N − 1 ans = 0,1,...,N-1 ans=0,1,...,N−1 T = ⌈ N 1 ⌉ l o g N + ⌈ N 2 ⌉ l o g N + ⋅ ⋅ ⋅ + ⌈ N n ⌉ l o g N = O ( N l o g 2 N ) T=\lceil \frac{N}{1} \rceil logN + \lceil \frac{N}{2} \rceil logN + ···+ \lceil \frac{N}{n} \rceil logN=O(Nlog^2N) T=⌈1N​⌉logN+⌈2N​⌉logN+⋅⋅⋅+⌈nN​⌉logN=O(Nlog2N)
전체 복잡 도 O (N l o g 2 N) O (Nlog ^ 2N) O (Nlog2N)
코드

#include
#define lc  u<<1
#define rc  u<<1|1
#define mid (t[u].l+t[u].r)/2
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;

int N;
int ans[MAX];
vector<int> store;

vector<int> g[MAX];
int anc[MAX][20], dep[MAX], st[MAX], ed[MAX], nodeOf[MAX], dfnt;
void dfs(int u, int fa) {
    dep[u] = dep[anc[u][0] = fa] + 1, nodeOf[st[u] = ++dfnt] = u;
    for (int i = 1; i <= 19; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto &v: g[u])
        if (v != fa) dfs(v, u);
    ed[u] = dfnt;
}
//k   ,    
int kthFa(int u, int k) { int bit = 0; while (k) { if (k & 1) u = anc[u][bit]; k >>= 1; bit++;} return u; }

struct SegmentTree {
    int mx, node, l, r;
    bool cover;
} t[MAX << 2];
void push_up(int u) {
    t[u].mx = 0;
    if (!t[lc].cover && t[lc].mx > t[u].mx) t[u].node = t[lc].node, t[u].mx = t[lc].mx;
    if (!t[rc].cover && t[rc].mx > t[u].mx) t[u].node = t[rc].node, t[u].mx = t[rc].mx;
}
void build(int u, int l, int r) {
    t[u].l = l, t[u].r = r;
    if (l == r) {
        t[u].mx = dep[t[u].node = nodeOf[l]];
        return;
    }
    build(lc, l, mid); build(rc, mid + 1, r);
    push_up(u);
}
void update(int u, int ql, int qr, int k) {
    if (ql <= t[u].l && t[u].r <= qr) {
        t[u].cover = k;
        return;
    }
    if (ql <= mid) update(lc, ql, qr, k);
    if (qr > mid) update(rc, ql, qr, k);
    push_up(u);
}


void init() {
    dfnt = 0;
    for (int i = 1; i <= N; i++) g[i].clear();
}

int main() {

    while (~scanf("%d", &N)) {
        init();
        for (int i = 2; i <= N; i++) {
            int x; scanf("%d", &x);
            g[x].push_back(i); g[i].push_back(x);
        }
        dep[0] = -1; dfs(1, 0);
        build(1, 1, dfnt);// dfs      
        for (int i = 1; i <= N; i++) ans[i] = N - 1;
        for (int nowans = N - 1; nowans >= 0; nowans--) {
            int cost = 0;
            store.clear();
            while (1) {
                cost++;
                if (t[1].mx <= nowans) break;//           <=ans,           
                int u = t[1].node;
                u = kthFa(u, nowans);//     u      nowans,    u   nowans  ,  u nowans-th  
                store.push_back(u);//        ,        
                update(1, st[u], ed[u], 1);//  u   ,      u     ,  u        <=nowans,          
            }
            ans[cost] = nowans;// cost       
            for (auto &i: store) update(1, st[i], ed[i], 0);//     
        }
        for (int i = 2; i <= N; i++) ans[i] = min(ans[i], ans[i - 1]);//               ,        
        ll sum = 0;
        for (int i = 1; i <= N; i++) sum += ans[i];
        printf("%lld
", sum);
    }



    return 0;
}