[Algebra for small w] (provide a solution for n^2 log)

Preface:

@CTHoi Blackie! Call!!!

But thanks to CTH for their great support and help in the realization of this question, otherwise it might not be tuned out now

Solution:

A word in lieu:Micromodified Line Segment Tree Merge Optimization on Round Square Trees DP。

think over\(O(n^3)\) "violent" practices:

For each node as the root run the dfs once to find out how many scenarios number of paths end at that point, and for each dfs carry out the following dp on the tree.

We're backtracking.Update father with child nodes, then it is equivalent to us solving for the decreasing path from the leaf to the root so that we can optimize.

found\(f_{i,j}\) expressed in terms of\(i\) in the subtree rooted at node no.\(j\) The answers for the endpoints have shifted as follows:

That way the tree part is done, but what about the area with the rings? As shown below:

Point 1 is the first point reached during the dfs process, and we refer to the first point reached by a dfs in the ring as theentry pointAt this point, we directly let the other points in the ring where point 1 is located run dfs, i.e., points 2 and 3, assuming that they are now all running out of the subtree with their own roots.\(f\) Array.

In reality, each point-rooted subtree in the ring other than the entry point may be traveled clockwise and counterclockwise once to the entry point, respectively.

So we enumerate each point as a starting point going to the right and to the left once each, maintaining an array each time\(A_i\) Indicates that the current scenario starts with\(i\) is the number of path schemes at the end.

Every time we go to a new point\(x\)The transfer is as follows:\(A' = A+f_x+\sum_{i=x+1}^n A_i\)。

This is not the right time complexity. As shown above, you end up with\(A\) The arrays are as follows:

It is easy to see that the contribution to the entry point is to go clockwise once counterclockwise once, minus the (repeated) original contribution of each subtree

Then we look at it as disconnecting the connecting edges of 1 and 2, and making one of the above transfers from the path 2 -> 3 -> 1;

In turn, the path from 3 -> 2 -> 1 is transferred again.

So the general idea is to run the subtrees of the other points in the ring first for each ring encountered, and then run each one clockwise counterclockwise to maintain the contribution of the subtrees in the ring to the incoming points.

Found it easy.\(n^3\) It's done, but lxyt said it well: "\(500^3\) It's sad," and Ratio said it well: "\(500^3\) Unless you constant is extremely small."

Considering optimization, we say that taking\(i\) The number of scenarios for a decreasing path with endpoints is\(i\) of the number of programs.

Every update\(u\) When the program of points is calculated, the\(u\) Point all child nodes\(v\) in the subtree of\(u\) the sum of the number of schemes for the points, and realized that this is actually simple interval summation, which can be maintained by a line tree.

• Instead, consider the tree transfer as a whole first:

  For each leaf point to open a line tree (dynamic opening point), then we open a line tree one point at a time from a\(v\) point back to the parent node\(u\) and updating it with a direct interval summation to find the\(v\) Within the subtree, the pair of\(u\) contribution, updating this contribution single point to the\(u\) on the tree of line segments and merge\(v\) of the line tree to the\(u\) Up.

• Ring transfer:

  Going through it clockwise along violent lines, merge the line tree of the points traveled through as well as the newly created contributions to a new line tree, and finally add the contributions to the incoming points to the line tree of the incoming points and merge the whole line tree up;

  Counterclockwise, to avoid repetition, we open the above one line tree as usual\(x\)and then open an additional line segment tree only to put the\(x\) The newly created contributions on this line tree during the transfer process are added without adding the portion of the line tree that each subtree already had.

Single point update and interval query single\(log\)The total number of dfs per dfs is\(O(n\log n)\), the overall complexity is\(O(n^2 \log n)\)。

code：

If you understand the idea, the code will be easy to write.

#include<bits/stdc++.h>
#define int long long
#define lson ls[rt]
#define rson rs[rt]
#define Aqrfre(x, y) freopen(#x ".in", "r", stdin),freopen(#y ".out", "w", stdout)
#define mp make_pair
#define Type int
#define qr(x) x=read()
typedef __int128 INT;
typedef long long ll;
using namespace std;

inline Type read(){
    char c=getchar(); Type x=0, f=1;
    while(!isdigit(c)) (c=='-'?f=-1:f=1), c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
    return x*f;
}

const int N = 505; 
const int M = 5e6;
const int mod = 998244353;

int n, m, tot, dis[N][N]; ll res;
vector<int>to[N], belong[N]; bool beA[N][N];

int top, th, s[N], bcc, low[N], dfn[N];
vector<int>BCC[N]; int sz[N];
inline void tarjan(int x, int p){
    s[++top] = x;
    low[x] = dfn[x] = ++th;
    for(int y : to[x]){
        if(!dfn[y]){
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if(low[y] == dfn[x]){
                ++bcc;
                do{ BCC[bcc].emplace_back(s[top]); sz[bcc]++;
                    belong[s[top]].emplace_back(bcc);
                    beA[s[top]][bcc] = true;
                }while(s[top--] != y);

                BCC[bcc].emplace_back(x); sz[bcc]++;
                belong[x].emplace_back(bcc);
                beA[x][bcc] = true;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

vector<int>tw[N][N];
ll v[M]; int rtot, ls[M], rs[M], root[M];
inline void pushup(int rt){
    v[rt] = (ll)(v[lson] + v[rson]) % mod;
} 

inline void update(int &rt, int l, int r, int pos, int val){
    if(!rt) rt = ++rtot;
    if(l == r){
        (v[rt] += val) %= mod;
        return;
    }

    int mid = (l + r) >> 1;
    if(pos <= mid) update(lson, l, mid, pos, val);
    else update(rson, mid+1, r, pos, val);

    pushup(rt);
}

inline int merge(int x, int y, int l, int r){
    if(!x or !y) return x + y;
    if(l == r){
        (v[x] += v[y]) %= mod;
        return x;
    }
    int mid = (l + r) >> 1;
    ls[x] = merge(ls[x], ls[y], l, mid);
    rs[x] = merge(rs[x], rs[y], mid+1, r);

    pushup(x); return x;
}

inline void mcpy(int &x, int y, int l, int r){
    if(!y) return;
    x = ++rtot;
    v[x] = v[y];
    if(l == r) return;
    
    int mid = (l + r) >> 1;
    mcpy(ls[x], ls[y], l, mid);
    mcpy(rs[x], rs[y], mid+1, r);
}

inline void mergeAdd(int &x, int y, int l, int r){
    if(!y) return;
    if(!x) x = (++rtot);
    if(l == r){
        (v[x] += v[y]) %= mod;
        return;
    }
    int mid = (l + r) >> 1;
    mergeAdd(ls[x], ls[y], l, mid);
    mergeAdd(rs[x], rs[y], mid+1, r);

    pushup(x); return;
}

inline int query(int rt, int l, int r, int pos){
    if(!rt) return 0;
    if(l >= pos){
        return v[rt] % mod;
    }
    int mid = (l + r) >> 1, res = 0;
    if(mid >= pos) res = query(lson, l, mid, pos);
    (res += query(rson, mid+1, r, pos)) %= mod;
    
    return res;
}

inline void watch(int rt, int l, int r){       
    int mid = l + r >> 1;
    if(ls[rt]) watch(lson, l, mid);
    if(rs[rt]) watch(rson, mid+1, r);
    if(rt) cout<<l<<" "<<r<<' '<<v[rt]<<'\n';
}

inline int qpos(int rt, int l, int r, int pos){
    if(l == r) return v[rt] % mod;
    int mid = (l + r) >> 1;
    if(mid >= pos) return qpos(lson, l, mid, pos);
    else return qpos(rson, mid+1, r, pos);
}

int ned, tem;
inline void dp(int x, int p, int goal, int whi, int op){
    if(x == goal) return;
    int num = 0;
    for(int y : tw[whi][x]){
        if(y == p) continue;

        num = query(root[ned], 1, n, y);

        mergeAdd(root[ned], root[y], 1, n);
        update(root[ned], 1, n, y, num);

        if(op == 1){
            update(root[tem], 1, n, y, num);
        }

        if(y == goal) break;
        dp(y, x, goal, whi, op);
    }
}

bool vis[N], flag[N];
inline void dfs(int x, int p, int bel){
    update(root[x], 1, n, x, 1);
    for(int whi : belong[x]){
        if(whi == bel) continue;
        if(flag[whi]) continue;
        flag[whi] = true;

        if(sz[whi] == 2){
            int num = 0;
            for(int y : tw[whi][x]){
                if(y == p or vis[y]) continue;
                vis[y] = true;
                dfs(y, x, whi);
                root[x] = merge(root[x], root[y], 1, n);
                num += query(root[y], 1, n, x);
            }
            update(root[x], 1, n, x, num);

            continue;
        }

        for(int i : BCC[whi]){
            if(x == i) continue;
            vis[i] = true;
            dfs(i, 0, whi);
        }
        
        int a = 0, b = 0;
        for(int i : tw[whi][x]){
            if(a) b = i;
            else a = i;
        }

        ned++; mcpy(root[ned], root[a], 1, n);
        dp(a, x, b, whi, 0);
        mergeAdd(root[x], root[ned], 1, n);
        update(root[x], 1, n, x, query(root[ned], 1, n, x));

        ned++; mcpy(root[ned], root[b], 1, n); tem = ned + 1;
        dp(b, x, a, whi, 1);
        mergeAdd(root[x], root[tem], 1, n);
        update(root[x], 1, n, x, query(root[tem], 1, n, x));
    }
}

inline void clean(){
    ned = max(ned, tem);
    fill(root+1, root+1+ned, 0);
    fill(flag, flag+1+n, 0);
    fill(vis, vis+1+n, 0);
    fill(ls, ls+1+rtot, 0);
    fill(rs, rs+1+rtot, 0);
    fill(v, v+1+rtot, 0);
    rtot = 0; ned = n;
}

signed main(){ //algebra
    Aqrfre(algebra, algebra);

    qr(n), qr(m); ned = n;
    for(int i=1; i<=m; i++){
        int qr(x), qr(y);
        dis[x][y] = dis[y][x] = 1;
        to[x].emplace_back(y);
        to[y].emplace_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!dfn[i]) tarjan(i, 0);

    for(int i=1; i<=bcc; i++)
        for(int x : BCC[i])
            for(int y : BCC[i]){
                if(x == y or !dis[x][y]) continue;
                tw[i][x].emplace_back(y);
            }


    int la = 0;
    for(int i=1; i<=n; i++){
        clean(); dfs(i, 0, 0);
        (res += qpos(root[i], 1, n, i)) %= mod;
    }

    cout<<res<<"\n";


    return 0;
}