BZOJ1095: [ZJOI2007]Hide 捉迷藏
动态树分治 点分治    2016-10-18 21:13:37    228    0    0

1095: [ZJOI2007]Hide 捉迷藏

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 2693  Solved: 1115
[Submit][Status][Discuss]

Description

  捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的
时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两
个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房
间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的
距离。

Input

  第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操作次数。接着Q行,每行一个操作,如
上文所示。

Output

  对于每一个操作Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的,输出0;若所有房间的灯都开着,输出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

HINT 

对于100%的数据, N ≤100000, M ≤500000。

 

Solution

题意就是求树上黑点间的最大距离

动态 树分治模板。。

考虑如果没有修改操作,我们点分治的时候维护子树内的最长路径,到重心的最长路径的最大值和次大值即可。

然后沿着这种思路,我们用堆维护上述两个信息,因为点分治树的深度为logN,所以每次修改操作最多只会修改到logN个结点,复杂度得以保证。

复杂度O(Q log^2 N)

 

/*{{{*/
#include <bits/stdc++.h>

#pragma GCC optimize("O2")
#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }
 
template <class T> inline T &read(T &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}
 
template <class T> void write(T x, char p = '\n') 
{
    register T tmp = 1;
    if (x < 0) putchar('-'), x = -x;
    while (x / tmp > 9) tmp *= 10;
    while (tmp) putchar(x / tmp + 48), x -= x / tmp * tmp, tmp /= 10;
    putchar(p);
}
/*}}}*/
 
const int mo = 1000000007;
const int oo = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int Lg = 20;

struct heap
{
    priority_queue<int> a, b;

    void push(int x) { a.push(x); }

    void erase(int x) { b.push(x); }

    int size() { return a.size() - b.size(); }

    int top() 
    {
        while (b.size() && a.top() == b.top()) {
            a.pop(); 
            b.pop(); 
        }
        if (a.size())
            return a.top();
        else
            return 0;
    }

    int top2() 
    {
        if (size() < 2) return 0;

        while (b.size() && a.top() == b.top()) {
            a.pop(); 
            b.pop(); 
        }

        int tmp = a.top(); a.pop();

        while (b.size() && a.top() == b.top()) {
            a.pop(); 
            b.pop(); 
        }

        int ret = a.top(); a.push(tmp);

        return ret;
    }

} ;

heap ans, B[maxn], C[maxn];

int st[maxn], cnte;
struct edge { int to, next; } e[maxn << 1];

inline void addedge(int u, int v)
{
    e[++ cnte] = {v, st[u]}; st[u] = cnte;
}
 
int n;
int m;
int tot_node;

bool vis[maxn];
bool color[maxn];

int size[maxn];

int dep[maxn];
int Fa[Lg][maxn], Divid_Fa[maxn];

static inline void PreDfs(int x, int fa)
{
    dep[x] = dep[fa] + 1;
    Fa[0][x] = fa;
    for (register int i = 1; i < Lg; ++ i)
        Fa[i][x] = Fa[i - 1][Fa[i - 1][x]];
    for (register int i = st[x]; i; i = e[i].next)
        if (e[i].to != fa)
            PreDfs(e[i].to, x);
}

static inline int LCA(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);

    for (register int i = 0, k = dep[u] - dep[v]; i < Lg; ++ i)
        if (k & (1 << i))
            u = Fa[i][u];

    if (u == v) return u;

    for (register int i = Lg - 1; ~i; -- i) {
        if (Fa[i][u] != Fa[i][v])
            u = Fa[i][u], v = Fa[i][v];
    }

    return Fa[0][u];
}

static inline int dis(int u, int v)
{
    return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

int Height_root;

static inline void GetSize(int x, int fa)
{
    size[x] = 1;
    for (register int i = st[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (fa != v && !vis[v]) {
            GetSize(v, x);
            size[x] += size[v];
        }
    }
}

static inline void GetRoot(int x, int fa)
{
    int mx = 0;
    for (register int i = st[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa && !vis[v]) {
            GetRoot(v, x);
            chkmax(mx, size[v]);
        }
    }
    chkmax(mx, tot_node - size[x]);
    if (mx <= tot_node / 2)
        Height_root = x;
}

static inline void Divid_Tree(int x, int fa)
{
    vis[x] = 1;
    Divid_Fa[x] = fa;
    for (register int i = st[x]; i; i = e[i].next) {
        int v = e[i].to;
        if (!vis[v]) {
            GetSize(v, x);
            tot_node = size[v];
            GetRoot(v, x);
            Divid_Tree(Height_root, x);
        }
    }
}

static inline void Be_Black(const int &height_root, const int &child)
{
    if (height_root == child) {
        B[height_root].push(0);
        if (B[height_root].size() == 2)
            ans.push(B[height_root].top());
    }

    if (!Divid_Fa[height_root])
        return;

    int father = Divid_Fa[height_root];
    int Dis = dis(father, child);

    int tmp = C[height_root].top();

    C[height_root].push(Dis);

    if (Dis > tmp) {
        int size = B[father].size();
        int tmp2 = B[father].top() + B[father].top2();
        if (tmp)
            B[father].erase(tmp);
        B[father].push(Dis);

        int now = B[father].top() + B[father].top2();

        if (now > tmp2) {
            if (size >= 2) 
                ans.erase(tmp2);
            if (B[father].size() >= 2) 
                ans.push(now);
        }
    }

    Be_Black(father, child);
}

static inline void Be_white(const int &height_root, const int &child)
{
    if (height_root == child) {
        if (B[height_root].size() == 2)
            ans.erase(B[height_root].top());
        B[height_root].erase(0);
    }

    if (!Divid_Fa[height_root])
        return;

    int father = Divid_Fa[height_root];
    int Dis = dis(father, child);

    int tmp = C[height_root].top();

    C[height_root].erase(Dis);

    if (Dis == tmp) {
        int size = B[father].size();
        int tmp2 = B[father].top() + B[father].top2();

        B[father].erase(Dis);
        if (C[height_root].top())
            B[father].push(C[height_root].top());

        int now = B[father].top() + B[father].top2();

        if (now < tmp2) {
            if (size >= 2) 
                ans.erase(tmp2);
            if (B[father].size() >= 2) 
                ans.push(now);
        }
    }

    Be_white(father, child);
}

// B : the longest path in the subtree of the height_root
// C : the longest path cross the height_root

void exec() 
{
    read(n);

    for (register int i = 1, u, v; i < n; ++ i) {
        read(u);
        read(v);
        addedge(u, v);
        addedge(v, u);
    }

    PreDfs(1, 0);

    tot_node = n;

    GetRoot(1, 0);
    Divid_Tree(Height_root, 0);


    for (register int i = 1; i <= n; ++ i) {
        color[i] = 1;
        C[i].push(0);
    }

    for (register int i = 1; i <= n; ++ i) {
        Be_Black(i, i);
    }

    int tot_black = n;

    for (read(m); m --; ) {
        static int x;
        static char s[2];
        scanf("%s", s);
        if (s[0] == 'G')
            write(tot_black <= 1 ? tot_black - 1 : ans.top());
        else {
            read(x);
            if (color[x])
                Be_white(x, x), -- tot_black;
            else
                Be_Black(x, x), ++ tot_black;
            color[x] ^= 1;
        }
    }

}


/*{{{*/
int main() 
{
    //ios::sync_with_stdio(false);

    if (fopen(iput.c_str(), "r")) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }
 
    exec();

#ifdef DEBUG_STATUS
    cerr << "\nRunning Time: " << (double) clock() / CLOCKS_PER_SEC << endl;
#endif

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/

 

BZOJ4237: 稻草人
228 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航