欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ1023 SHOI2008 仙人掌图 仙人掌、单调队列

程序员文章站 2022-05-22 10:06:45
...

传送门


求仙人掌的直径,可以由求树的直径进行拓展,只需要在环上特殊判断。

沿用求树的直径的DP,对于一条不在任何环内的边,直接像树的直径一样转移,然后考虑环的影响。

设环长为\(cir\),在\(dfs\)树上,环对应的链的链顶为\(top\),链底为\(bot\),也就是说返祖边为\((top,bot)\),点\(x\)\(dfs\)树上的深度为\(dep_x\)

在统计环上的点之间的转移和贡献之前,先把环上所有点的子仙人掌的贡献统计好。

环上的转移直接通过方程式\(dp_{top} \leftarrow dp_{u} + \min\{dep_u - dep_{top} , cir - dep_u + dep_{top}\}\)从所有点转移到链顶

考虑如何统计环上的贡献,相对来说是比较难的一部分。

对于在环上的两个点\(u,v(dep_u > dep_v)\),它们对答案的贡献为\(dp_u + dp_v + \min\{dep_u - dep_{v} , cir - dep_u + dep_{v}\}\)

我们考虑将\(dp_u +dp_v + dep_u - dep_v\)\(dp_u + dp_v + cir + dep_v - dep_u\)的贡献分开计算。下面只说\(dp_u + dp_v + dep_u - dep_v\)的情况,另一种计算同理。

我们考虑按照深度从大往小加点,那么如果对于两个点\(i,j\)满足\(dep_i < dep_j \&\& dep_i + dp_i \geq dep_j + dp_j\),表示\(i\)相比于\(j\)能够对更多的点产生贡献,而且转移更优,那么\(j\)就是没有必要的了。可以发现转移满足单调队列优化的性质,使用单调队列优化转移即可。记得转移需要满足\(dep_u - dep_v < cir + dep_v - dep_u\),如果队首不满足这个条件需要删除。

#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;

inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c) && c != EOF){
        if(c == '-')
            f = 1;
        c = getchar();
    }
    if(c == EOF)
        exit(0);
    while(isdigit(c)){
        a = a * 10 + c - 48;
        c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 1e5 + 10;
struct Edge{
    int end , upEd;
}Ed[MAXN << 2];
int head[MAXN] , dp[MAXN] , dep[MAXN] , fa[MAXN] , ch[MAXN];
int N , M , cntEd , ans;
deque < int > q;

inline void addEd(int a , int b){
    Ed[++cntEd].end = b;
    Ed[cntEd].upEd = head[a];
    head[a] = cntEd;
}

void calc(int top , int bot){
    int cir = dep[bot] - dep[top] + 1 , p = bot;
    q.push_back(bot);
    do{
        ch[fa[p]] = p;
        p = fa[p];
        int t = q.front();
        if(dep[t] - dep[p] > cir - dep[t] + dep[p]){
            q.pop_front();
            t = q.front();
        }
        ans = max(ans , dep[t] - dep[p] + dp[t] + dp[p]);
        while(!q.empty() && dep[q.back()] + dp[q.back()] <= dep[p] + dp[p])
            q.pop_back();
        q.push_back(p);
    }while(p != top);
    q.clear();
    int p1 = top;
    p = bot;
    q.push_back(p1);
    while(cir - dep[p] + dep[top] <= dep[p] - dep[top])
        p = fa[p];
    do{
        p1 = ch[p1];
        p = ch[p];
        int t = q.front();
        ans = max(ans , cir + dep[t] - dep[p] + dp[t] + dp[p]);
        while(!q.empty() && dep[q.back()] + dp[q.back()] <= dep[p1] + dp[p1])
            q.pop_back();
        q.push_back(p1);
    }while(p != bot);
    q.clear();
    p = bot;
    while(p != top){
        dp[top] = max(dp[top] , dp[p] + min(dep[p] - dep[top] , cir + dep[top] - dep[p]));
        p = fa[p];
    }
}

int dfs(int x , int p){
    fa[x] = p;
    dep[x] = dep[p] + 1;
    int t = 0;
    for(int i = head[x] ; i ; i = Ed[i].upEd)
        if(Ed[i].end != p)
            if(dep[Ed[i].end])
                if(dep[Ed[i].end] < dep[x])
                    t = Ed[i].end;
                else
                    calc(x , Ed[i].end);
            else{
                int q = dfs(Ed[i].end , x);
                if(!q){
                    ans = max(ans , dp[x] + dp[Ed[i].end] + 1);
                    dp[x] = max(dp[x] , dp[Ed[i].end] + 1);
                }
                else
                    if(q != x)
                        t = q;
            }
    return t;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
#endif
    N = read();
    M = read();
    for(int i = 1 ; i <= M ; ++i){
        int L = read() , a = read();
        for(int i = 2 ; i <= L ; ++i){
            int b = read();
            addEd(a , b);
            addEd(b , a);
            a = b;
        }
    }
    dfs(1 , 0);
    cout << ans;
    return 0;
}