9.28-9.29做题总结

这两日的题是极难的。 —— 9.25-9.26做题总结

9.28

A 会议选址

巨大码量题。

容易发现每次向代表和最多的子树走就能走到最优解的位置。

然后发现这样做显然复杂度爆炸，考虑优化。

因为代表的下标区间是连续的，可以使用主席树（相当于线段树前缀和）来维护每个代表，然后查询的时候就可以做差分。

使用树分治加速，但是因为可能会有菊花图来卡，需要进行一个三度化来保证复杂度。

细节的话记得三度化开四倍空间。

代码比较长，所以贴一下（

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 100010
int n,q;
vector<int>g[N];
struct Tree{
    int ls,rs;
    int sum;
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
}t[N * 40];
int pcnt;
void modify(int &p,int l,int r,int x)
{
    t[++pcnt] = t[p];
    p = pcnt;
    t[p].sum++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(mid >= x) modify(ls(p),l,mid,x);
    else modify(rs(p),mid+1,r,x);
}
 
int query(int p,int l,int r,int x,int y)
{
    if(x <= l && r <= y) return t[p].sum;
    int mid = (l + r) >> 1,res = 0;
    if(mid >= x) res += query(ls(p),l,mid,x,y);
    if(mid < y) res += query(rs(p),mid+1,r,x,y);
    return res;
}
 
int rt[N];
 
namespace edt{
vector<int> t1[N << 2],t2[N << 2];
int t3[N << 2][2];
 
void build(int u,int fa)
{
    for(int v : g[u])
    {
        if(v == fa) continue;
        t1[u].push_back(v);
        build(v,u);
    }
}
 
struct edge{
    int u,v,w;
    edge(){}
    edge(int _u,int _v,int _w) : 
    u(_u),v(_v),w(_w){}
};
vector<edge> e;
 
inline void addE(int u,int v,int w)
{
    t2[u].push_back(e.size());
    e.emplace_back(u,v,w);
    t2[v].push_back(e.size());
    e.emplace_back(v,u,w);
}
 
int pcnt;
int ori[N << 2];
 
void rebuild(int u)
{
    if(t1[u].size() <= 2)
    {
        for(auto v : t1[u])
        {
            addE(u,v,1);
            rebuild(v);
        }
    }
    else
    {
        int s1 = ++ pcnt,s2 = ++pcnt;
        ori[s1] = ori[s2] = ori[u];
        for(int i = 0;i < t1[u].size();i++)
        {
            if(i & 1) t1[s1].push_back(t1[u][i]);
            else t1[s2].push_back(t1[u][i]);
        }
        addE(u,s1,0),addE(u,s2,0);
        rebuild(s1),rebuild(s2);
    }
}
 
int dep[N << 2];
int st[N << 2],ed[N << 2];
int stamp;
 
void dfs(int u,int fa)
{
    st[u] = ++stamp;
    for(int eid : t2[u])
    {
        int v = e[eid].v;
        if(v == fa) continue;
        dep[v] = dep[u] + 1;
        dfs(v,u);
    }
    ed[u] = stamp;
}
 
bool vis[N << 2];
int siz[N << 2];
int rt,mns;
 
void findrt(int u,int fa,int tots)
{
    siz[u] = 1;
    for(int eid : t2[u])
    {
        if(vis[eid >> 1]) continue;
        int v = e[eid].v;
        if(v == fa) continue;
        findrt(v,u,tots);
        siz[u] += siz[v];
        int ns = max(siz[v],tots - siz[v]);
        if(ns < mns) mns = ns,rt = eid;
    }
}
 
vector<pair<int,long long>> lst[N << 2][2];
 
int dis[N << 2][25];
 
void calc(int u,int d,vector<pair<int ,long long>> &l,int fa)
{
    if(u <= n) l.emplace_back(u,dis[u][d]);
    for(int eid : t2[u])
    {
        if(vis[eid >> 1]) continue;
        int v = e[eid].v,w = e[eid].w;
        if(v == fa) continue;
        dis[v][d] = dis[u][d] + w;
        calc(v,d,l,u);
    }
}
 
int divide(int p,int tots,int d)
{
    mns = INT_MAX,findrt(p,0,tots);
    if(mns == INT_MAX) return -1;
    int nrt = rt,rrt = nrt ^ (nrt & 1),id = rrt >> 1;
    int u = e[rrt].u,v = e[rrt].v;
    vis[id] = true;
    calc(u,d,lst[id][0],0);
    calc(v,d,lst[id][1],0);
    lst[id][0].emplace_back(0,0);
    lst[id][1].emplace_back(0,0);
    sort(lst[id][0].begin(),lst[id][0].end());
    sort(lst[id][1].begin(),lst[id][1].end());
    for(int i = 1;i < lst[id][0].size();i++) lst[id][0][i].second += lst[id][0][i - 1].second;
    for(int i = 1;i < lst[id][1].size();i++) lst[id][1][i].second += lst[id][1][i - 1].second;
    if(nrt & 1)
    {
        t3[id][0] = divide(u,siz[u],d + 1);
        t3[id][1] = divide(v,tots - siz[u],d + 1);
    }
    else
    {
        t3[id][0] = divide(e[rrt].u,tots - siz[v],d + 1);
        t3[id][1] = divide(e[rrt].v,siz[v],d + 1);
    }
    return id;
}
 
int res;
struct route{
    int eid,d,dir;
    route(){}
    route(int _e,int _d,int _dir) : 
    eid(_e),d(_d),dir(_dir){}
};
 
vector<route> rte;
void find(int eid,int rt1,int rt2,int siz,int d)
{
    if(eid == -1) return;
    int u = e[eid << 1].u,v = e[eid << 1].v;
    int c = query(rt2,1,pcnt,st[v],ed[v]) - query(rt1,1,pcnt,st[v],ed[v]);
    if(c > (siz >> 1))
    {
        rte.emplace_back(eid,d,1);
        res = v,find(t3[eid][1],rt1,rt2,siz,d + 1);
    }
    else if(siz - c >= (siz >> 1))
    {
        rte.emplace_back(eid,d,0);
        res = u,find(t3[eid][0],rt1,rt2,siz,d + 1);
    }
}
 
long long recall(int l,int r)
{
    long long sum = 0;
    for(const auto & p : rte)
    {
        int eid = p.eid,dir = p.dir ^ 1,d = p.d;
        auto itr = --lower_bound(lst[eid][dir].begin(),lst[eid][dir].end(),pair<int,long long>(r + 1,0ll));
        auto itl = --lower_bound(lst[eid][dir].begin(),lst[eid][dir].end(),pair<int,long long>(l,0ll));
        sum += itr -> second - itl -> second + 1ll * (itr - itl) * (dis[res][d] + e[eid << 1].w);
    }
    rte.clear();
    return sum;
}
 
}
 
void main()
{
    scanf("%d%d",&n,&q);
    for(int i = 1;i < n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].emplace_back(v),g[v].emplace_back(u);
    }
    edt :: build(1,0);
    for(int i = 1;i <= n;i ++) 
        edt :: ori[i] = i;
    edt :: pcnt = n,edt :: rebuild(1);
    edt :: dfs(1,0);
    int drt = edt :: divide(1,edt :: pcnt,0);
    for(int i = 1;i <= n;i++) rt[i] = rt[i-1],modify(rt[i],1,edt :: pcnt,edt :: st[i]);
    for(int i = 1;i <= q;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        edt :: find(drt,rt[l - 1],rt[r],r - l + 1,0);
        printf("%lld\n",edt :: recall(l,r));
    }
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B Combining Slimes

CF618G Combining Slimes

神仙期望DP

赛时看数据范围直接想到矩阵加速递推——实际上也是这样。

但是不会写DP式子，期望DP这块很薄弱所以不很改的动

C A Stroll Around the Matrix

CF1609G A Stroll Around the Matrix

区间加等差数列并且求一个离谱东西。

差分数组单调递增是个好性质，这样的话对于最后的矩阵每次只需要向差分小的方向去走就行，这个贪心比较易证。

所以对于b直接存差分数组，区间加等差数列就变成了后缀区间加法。

a很小所以直接暴力，，统计答案的时候直接把a的差分值“插入”到b的差分值中。

因为每次向差分值小的方向走所以其实就是把两个差分数组一起排个序。

使用线段树二分可以实现这个操作。

写了代码所以就放一下 ：

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
namespace fast_IO
{
    #define FAST_IO
    #define IOSIZE 100000
    typedef long long ll;
    typedef double DB;
    typedef long double lDB;
    typedef __int128_t i128;
    char ibuf[IOSIZE], obuf[IOSIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
    #ifdef ONLINE_JUDGE
        #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
        #define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif//fread in OJ, stdio in local

    #define isdigit(ch) (ch>47&&ch<58)
    #define isspace(ch) (ch<33&&ch!=EOF)
    
    struct fast_IO_t {
        ~fast_IO_t() {
            fwrite(obuf, p3-obuf, 1, stdout);
        }
        bool flag = false;
        operator bool() {
            return flag;
        }
    }io;
    
    template<typename T> inline T read() {
        T s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return 0;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (DB)flt/pow(10,cnt);
        }
        return s *= w;
    }
    template<typename T> inline bool read(T &s) {
        s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return false;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (DB)flt/pow(10,cnt);
        }
        return s *= w, true;
    }
    inline bool read(char &s) {
        while(s = getchar(), isspace(s));
        return s != EOF;
    }
    inline bool read(char *s) {
        char ch;
        while(ch=getchar(), isspace(ch));
        if(ch == EOF) return false;
        while(!isspace(ch))
            *s++ = ch, ch=getchar();
        *s = '\000';
        return true;
    } 
    template<typename T> void print(T x) {
        static int t[20]; int top = 0;
        if(x < 0) putchar('-'), x = -x;
        do { t[++top] = x%10; x /= 10; } while(x);
        while(top) putchar(t[top--]+48);
    }
    struct empty_type{}; int pcs = 8;
    empty_type setpcs(int cnt) {
        return pcs = cnt, empty_type();
    }
    inline void print(empty_type x){}
    inline void print(double x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((ll)(x)); x -= (ll)(x);
        if(pcs != 0) putchar('.');
        for(int i = 1; i <= pcs; i++)
        x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(float x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((ll)(x)); x -= (ll)(x);
        if(pcs != 0) putchar('.');
        for(int i = 1; i <= pcs; i++)
        x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(long double x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((i128)(x)); x -= (i128)(x);
        if(pcs != 0) putchar('.');
        for(int i = 1; i <= pcs; i++)
        x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(char x) {
        putchar(x);
    }
    inline void print(char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    inline void print(const char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    #ifdef _GLIBCXX_STRING//string
        inline bool read(std::string& s) {
            s = ""; char ch;
            while(ch=getchar(), isspace(ch));
            if(ch == EOF) return false;
            while(!isspace(ch))
                s += ch, ch = getchar();
            return true;
        }
        inline void print(std::string x) {
            for(string::iterator i = x.begin(); i != x.end(); i++)
                putchar(*i);
        }
        inline bool getline(fast_IO_t &io, string s) {
            s = ""; char ch = getchar();
            if(ch == EOF) return false;
            while(ch != '\n' and ch != EOF)
                s += ch, ch = getchar();
            return true;
        }
    #endif
    #if __cplusplus >= 201103L
        template<typename T, typename... T1>
        inline int read(T& a, T1& ...other) {
            return read(a)+read(other...);
        }
        template<typename T, typename... T1>
        inline void print(T a, T1... other) {
            print(a); print(other...);
        }
    #endif
    template<typename T>
    fast_IO_t& operator >> (fast_IO_t &io, T &b) {
        return io.flag=read(b), io;
    }
    fast_IO_t& operator >> (fast_IO_t &io, char *b) {
        return io.flag=read(b), io;
    }
    template<typename T>
    fast_IO_t& operator << (fast_IO_t &io, T b) {
        return print(b), io;
    }
    #define cout io
    #define cin io
    #define endl '\n'
}
using namespace fast_IO;
#define N 110
#define M 100010
typedef long long ll;

struct Tree{
    ll sum;
    int l,r;
    ll lz,maxx;
    int len() {return r - l + 1;}
}t[M << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

ll a[N];
ll da[N];
ll b[M];
ll db[M];
ll ans;
ll s;
int n,m,q;

void push_up(int x);
void push_down(int x);
ll query(int x,int l,int r);
void build(int x,int l,int r);
int binary_search(int x,ll val);
void change(int x,int l,int r,ll k);

void main()
{
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= m;i++) cin >> b[i];
    for(int i = 2;i <= n;i++) da[i] = a[i] - a[i-1];
    for(int i = 2;i <= m;i++) db[i] = b[i] - b[i-1];
    for(int i = 2;i <= m;i++) s += db[i] * (m - i + 1);
    ll opt,k,d;
    build(1,2,m);
    for(int i = 1;i <= q;i++)
    {
        cin >> opt >> k >> d;
        if(opt == 1)
        {
            if(k == n)
            {
                a[1] += d;
                k--;
            }
            for(int i = n - k + 1;i <= n;i++) da[i] += d;
        }
        else
        {
            if(k == m)
            {
                b[1] += d;
                k--;
            }
            s += d * (k * (k + 1) / 2);
            change(1,m - k + 1,m,d);
        }
        ans = s + (n + m - 1) * (a[1] + b[1]);
        ll sum = query(1,2,m);
        ll _ = query(1,m,m);
        for(int i = 2;i <= n;i++)
        {
            if(_ < da[i])
            {
                ans += sum;
                continue;
            }
            int pos = binary_search(1,da[i]);
            if(pos != 2) ans += query(1,2,pos-1);
            ans += da[i] * (m - pos + 1);
        }
        for(int i = 2;i <= n;i++) ans += da[i] * (n - i + 1);
        cout << ans << endl;
    }
    return;
}

int binary_search(int x,ll val)
{
    if(t[x].l == t[x].r) return t[x].l;
    push_down(x);
    if(t[ls(x)].maxx >= val) return binary_search(ls(x),val);
    else return binary_search(rs(x),val);
}

ll query(int x,int l,int r)
{
    if(t[x].l >= l && t[x].r <= r) return t[x].sum;
    ll ans = 0;
    push_down(x);
    if(t[ls(x)].r >= l) ans += query(ls(x),l,r);
    if(t[rs(x)].l <= r) ans += query(rs(x),l,r);
    return ans;
}

void change(int x,int l,int r,ll k)
{
    if(t[x].l >= l && t[x].r <= r)
    {
        t[x].sum += t[x].len() * k;
        t[x].lz += k;
        t[x].maxx += k;
        return;
    }
    push_down(x);
    if(t[ls(x)].r >= l) change(ls(x),l,r,k);
    if(t[rs(x)].l <= r) change(rs(x),l,r,k);
    push_up(x);
}

void build(int x,int l,int r)
{
    t[x].l = l,t[x].r = r;
    if(l == r)
    {
        t[x].sum = t[x].maxx = db[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    push_up(x);
}

inline void push_down(int x)
{
    t[ls(x)].maxx += t[x].lz;
    t[rs(x)].maxx += t[x].lz;
    t[ls(x)].lz += t[x].lz;
    t[rs(x)].lz += t[x].lz;
    t[ls(x)].sum += t[ls(x)].len() * t[x].lz;
    t[rs(x)].sum += t[rs(x)].len() * t[x].lz;
    t[x].lz = 0;
}

inline void push_up(int x)
{
    t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
    t[x].maxx = t[rs(x)].maxx;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

9.29

A

EB : 神仙DP题

竟然是一个树上背包

对于 $k \le 2$ 的情况可以进行一个贪心的做，能做到 $O(n)$ 。

剩下的情况使用DP，可以利用性质来判断当有两个以上或少量分身进入同一棵子树之后的必然状态，会使总的状态数大大减少。

实际上可以枚举边，可以省去反复枚举点的重复状态。

枚举边 $(x,y)$ ，计算以 $y$ 为父节点， $x$ 为根的子树的 DP 值，即可反复利用。

B

求有向图邻接矩阵的幂敛指数与周期

第一次写布尔矩阵板子，总之是没有写挂。

对于周期的求法是这样的 :

对于每个强连通分量它的周期是其中每个环长度的 $\gcd$ ，而整张图的周期是所有强连通分量周期的 $\text{lcm}$ ，证明我只能感性理解所以不给出。

然后套个 tarjan 板子就能求这一部分了。

求幂敛指数的部分就必须建出邻接矩阵，因为是布尔矩阵可以直接用 std :: bitset 分别存行和列，这样矩阵乘法的就只需要两个 for 循环，实际上大概是可以认为时间除了一个 $32$ 的常数。

虽然不写这个优化也能过，但是写了肯定更快（至少在 $O_2$ ）之下。

幂敛指数显然可以二分，所以用二分或者倍增的写法都行。我开始写了倍增然后写挂了所以改成二分。

实际上二分的实现难度要小。

要注意的是因为周期要对 $1e9+7$ 取模，所以在要在求 $\text{lcm}$ 的时候拆因子再起来，但是为了避免取模对后边的 check 造成影响必须在合并因子的同时处理出来邻接矩阵的周期次方。然后就没啥细节了。

放一下代码，主要是里边有个结构体实现的布尔矩阵板子。

用法的话重载了下标运算符，但是修改元素要使用 set(int x,int y,bool val) 函数，因为要同时修改行的值和列的值。

可以使用 print() 函数来输出矩阵

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 100010
typedef long long ll;
#define int long long
const ll mod = 1e9 + 7;
#define file
#define N 100010
#define SIZE 200

struct matrix
{
    int n,m;
    bitset<SIZE>r[SIZE],c[SIZE];
    void init(){memset(r,0,sizeof(r));memset(c,0,sizeof(c));}
    matrix(){}
    matrix(int _n,int _m):n(_n),m(_m){init();}
    bitset<SIZE>* operator[] (int x)
    {
        return &r[x];
    }
    friend matrix operator * (matrix x,matrix y)
    {
        matrix ans(x.n,y.m);
        for(int i = 0;i < x.n;i++)
        for(int j = 0;j < y.m;j++)
            ans.set(i,j,(x.r[i] & y.c[j]).any());
        return ans;
    }
    friend matrix operator + (matrix x,matrix y)
    {
        for(int i = 0;i<x.n;i++)
        for(int j = 0;j<x.m;j++)
        {
            x[i][j] |= y[i][j];
        }
        return x;
    }
    friend bool operator == (matrix a,matrix b)
    {
        if(a.n != b.n || a.m != b.m) return false;
        for(int i = 0;i < a.n;i++)
            if(a.c[i] != b.c[i]) return false;
        return true;
    }
    friend bool operator != (matrix a,matrix b)
    {
        return !(a == b);
    }
    matrix& operator = (int _a[SIZE][SIZE])
    {
        this -> n = SIZE,this -> m = SIZE;
        for(int i = 0;i < this -> n;i++)
        for(int j = 0;j < this -> m;j++)
            this -> set(i,j,_a[i][j]);
        return *this;
    }
    void set(int x,int y,bool a)
    {
        r[x][y] = c[y][x] = a;
    }
    void print()
    {
        for(int i = 0;i < n;i ++ ,puts(""))
        for(int j = 0;j < m;j++)
        printf("%d ",r[i][j] ? 1 : 0);
    }
}a,b;

matrix ksm(matrix a,ll b)
{
    matrix ans = a;b--;
    if(b < 0) return a;
    for(;b;b>>=1,a = a * a) if(b & 1) ans = ans * a;
    return ans;
}

int n,m,t;
vector<int> G[N];
int dfn[N],low[N],dfntot;
int col[N],coltot;
bool in_sta[N];
int sta[N],top;
bool lai[N];
int dep[N],g;
bool vis[N];
vector<int> fin;
set<int> pri;
int tme[N];
ll tmp;

bool check(ll mid)
{
    return ksm(b,mid) == ksm(b,mid) * a;
}

ll lcm(ll x,ll y) {return x * y / __gcd(x,y);}
ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b >>= 1,a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}

void tarjan(int x);
void dfs(int x,int ncol);

void main()
{
    scanf("%lld%lld%lld",&n,&m,&t);
    if(t)
        a = matrix(n,n);
    int u,v;
    for(int i = 1;i <= m;i++)
    {
        scanf("%lld%lld",&u,&v);
        G[u].emplace_back(v);
        if(t)
        a.set(u-1,v-1,1);
    }
    for(int i = 1;i <= n;i++) 
        if(!dfn[i]) tarjan(i);
    for(int i = 1;i <= n;i++)
        if(!vis[col[i]])
        {
            vis[col[i]] = true;
            g = 0;
            dfs(i,col[i]);
            if(!g) continue;
            fin.emplace_back(g);
        }
    for(auto now : fin)
    {
        int nn = now;
        for(int i = 2;i * i <= nn;i++)
        {
            int res = 0;
            while(nn % i == 0) res++, nn /= i;
            if(res) pri.insert(i);
            tme[i] = max(res,tme[i]);
        }
        if(nn != 1) 
        {
            pri.insert(nn);
            tme[nn] = max(tme[nn],1ll);
        }
    }
    tmp = 1;
    if(t) b = a;
    for(auto it : pri)
    {
        tmp = tmp * ksm(it,tme[it]) % mod;
        a = ksm(a,ksm(it,tme[it]));
    }
    if(!t)
    {
        printf("%lld",tmp);
        return;
    }
    int k = 1;
    ll l = 1,r = 1ll << 21;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld %lld",l,tmp);
    return;
}

void dfs(int x,int ncol)
{
    lai[x] = true;
    for(auto y : G[x])
    {
        if(col[y] != ncol) continue;
        if(lai[y])
        {
            if(!g) g = dep[x] - dep[y] + 1;
            else if(dep[x] - dep[y] + 1) g = __gcd(g,abs(dep[x] - dep[y] + 1));
            continue;
        }
        dep[y] = dep[x] + 1;
        dfs(y,ncol);
    }
}

void tarjan(int x)
{
    low[x] = dfn[x] = ++dfntot;
    sta[++top] = x;
    in_sta[x] = true;
    for(auto v : G[x])
    {
        if(!dfn[v]) tarjan(v),low[x] = min(low[x],low[v]);
        else if(in_sta[v]) low[x] = min(low[x],dfn[v]);
    }
    if(low[x] == dfn[x])
    {
        coltot++;
        int y;
        do
        {
            y = sta[top--];
            in_sta[y] = false;
            col[y] = coltot;
        }
        while(y != x);
    }
}

}

signed main()
{
#ifdef file
    freopen("lost.in","r",stdin);
    freopen("lost.out","w",stdout);
#endif
    Pozhu :: main();
    return 0;
}

C

体型巨大的数据结构题。

有三十分暴力分， $O(n^2)$ 暴力怎么写都行。

菊花图的分很好拿，用线段树维护最大值即可

链的部分分我觉得要难一点。对于每一条路径，中间区间 $max$ ，两个端点打标记，，最后扫一遍更新最大值。

正解是考虑一条路径会对哪些位置有贡献，进行一个分别的维护。结果是码量巨大。