[ZJOI 2007] 捉迷藏

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[ZJOI 2007] 捉迷藏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

[题目连接]php

       https://www.lydsy.com/JudgeOnline/problem.php?id=1095c++

[算法]git

        首先建出点分树,而后每个点开两个堆。“第一个堆记录子树中全部节点到父亲节点的距离 ,第二个堆记录全部子节点的堆顶 ,那么一个节点的堆2中的最大和次大加起来就是子树中通过这个节点的最长链。而后咱们最后开一个全局的堆,记录全部堆2中最大值和次大值之和。那么全局的堆顶就是答   算法

        案ide

        时间复杂度 : O(NlogN ^ 2)spa

[代码]get

        

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 500010
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n , root , tot , timer;
int size[N] , head[N] , weight[N] , father[N] , ans[N];
bool visited[N] , light[N];
map< int , pair<int , int> > mp[N];

struct edge
{
        int to , nxt;
} e[M << 1];

struct Heap
{
        priority_queue< int > hp , era;
        inline void ins(int value)
        {
                hp.push(value);
        }
        inline void del(int value)
        {
                if (value != 0) era.push(value);
        }
        inline int max()
        {
                while (!hp.empty() && !era.empty() && era.top() == hp.top())
                {
                        hp.pop();
                        era.pop();
                }
                if (hp.empty()) return 0;
                else return hp.top();
        }
        inline int secmax()
        {
                int tmp = max();
                del(tmp);
                int ret = max();
                ins(tmp);
                return ret;
        }
} A , B[N] , C[N << 1];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}
inline void addedge(int u , int v)
{
        ++tot;
        e[tot] = (edge){v , head[u]};
        head[u] = tot;
}
inline void getroot(int u , int father , int total)
{
        size[u] = 1;
        weight[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt)
        {
                int v = e[i].to;
                if (v == father || visited[v]) continue;
                getroot(v , u , total);
                size[u] += size[v];
                chkmax(weight[u] , size[v]);
        }
        chkmax(weight[u] , total - size[u]);
        if (weight[u] < weight[root]) root = u;        
}
inline void dfs(int u , int father , int rt , int belong , int depth)
{
        mp[rt][u] = make_pair(belong , depth);
        C[belong].ins(depth);
        for (int i = head[u]; i; i = e[i].nxt)
        {
                int v = e[i].to;
                if (v == father || visited[v]) continue;
                dfs(v , u , rt , belong , depth + 1);
        }
}
inline void work(int u)
{
        visited[u] = true;
        for (int i = head[u]; i; i = e[i].nxt)
        {
                int v = e[i].to;
                if (!visited[v]) 
                {
                        dfs(v , u , u , ++timer , 1);
                        B[u].ins(C[timer].max());
                }
        }        
        ans[u] = B[u].max() + B[u].secmax();
        A.ins(ans[u]);
        for (int i = head[u]; i; i = e[i].nxt)
        {
                int v = e[i].to;
                if (!visited[v])
                {
                        root = 0;
                        getroot(v , u , size[v]);
                        father[root] = u;
                        work(root);
                }
        }
}

int main()
{
        
        read(n);
        for (int i = 1; i < n; i++)
        {
                int x , y;
                read(x); read(y);
                addedge(x , y);
                addedge(y , x);
        }
        int q;
        read(q);
        root = 0;
        weight[0] = n;
        getroot(1 , 0 , n);
        work(root);
        int cnt = n;
        while (q--)
        {
                char type[5];
                scanf("%s" , type);
                if (type[0] == 'C')
                {
                        int x , y;
                        scanf("%d" , &x);
                        y = x;
                        if (light[x])
                        {
                                light[x] = false;
                                ++cnt;
                                A.del(ans[x]);
                                ans[x] = B[x].max() + B[x].secmax();
                                A.ins(ans[x]);
                                x = father[x];
                                while (x != 0)
                                {
                                        pair<int , int> tmp = mp[x][y];
                                        B[x].del(C[tmp.first].max());
                                        C[tmp.first].ins(tmp.second);
                                        B[x].ins(C[tmp.first].max());
                                        A.del(ans[x]);
                                        if (light[x])
                                        {
                                                if (B[x].secmax()) ans[x] = B[x].max() + B[x].secmax();
                                                else ans[x] = 0;
                                        } else ans[x] = B[x].max() + B[x].secmax();
                                        A.ins(ans[x]);
                                        x = father[x];
                                }
                        } else
                        {
                                light[x] = true;
                                --cnt;
                                A.del(ans[x]);
                                if (B[x].secmax()) ans[x] = B[x].max() + B[x].secmax();
                                else ans[x] = 0;
                                A.ins(ans[x]);
                                x = father[x];
                                while (x != 0)
                                {
                                        pair<int , int> tmp = mp[x][y];
                                        B[x].del(C[tmp.first].max());
                                        C[tmp.first].del(tmp.second);
                                        B[x].ins(C[tmp.first].max());
                                        A.del(ans[x]);
                                        if (light[x])
                                        {
                                                if (B[x].secmax()) ans[x] = B[x].max() + B[x].secmax();
                                                else ans[x] = 0;
                                        } else ans[x] = B[x].max() + B[x].secmax();
                                        A.ins(ans[x]);
                                        x = father[x];
                                }
                        }
                 } else
                 {
                         if (!cnt) printf("-1\n");
                        else if (cnt == 1) printf("0\n");
                        else printf("%d\n" , A.max());        
                }
        }
        return 0;
    
}