This analysis covers problems involving interval graphs on cycles and string covering patterns.

Maximum Clique in a Circular Interval Graph Given intervals placed on a circle, where an edge connects two intervals if they intersect, the objective is to find the largest clique. For intervals on a line, the maximum clique size equals highest point coverage count. Breaking the circle at a chosen point transforms the problem. Let intervals crossing this breakpoint be set A, and others be set B. Within set B, any maximum clique must share a common intersection point. The problem reduces to selecting a common point for set B intervals while including all compatible intervals from set A. This is a bipartite maximum independent set problem, where edges represent conflicts defined by 2D partial order. A greedy flow algorithm resolves this in O(n log n). The total complexity is O(n² log n).

#include <bits/stdc++.h>
using namespace std;
struct Interval { int l, r; };
vector<Interval> cross, noncross;
vector<int> add[1000001], rem[1000001];
bool active[2001];
int main() {
    ios::sync_with_stdio(false);
    int tests; cin >> tests;
    while(tests--) {
        int n; cin >> n;
        cross.clear(); noncross.clear();
        for(int i = 0; i < n; i++) {
            int a, b; cin >> a >> b;
            if(b == 1000000) cross.push_back({0, a});
            else if(a > b) cross.push_back({b, a});
            else noncross.push_back({a, b});
        }
        sort(cross.begin(), cross.end(), [](Interval x, Interval y){ return x.l < y.l; });
        sort(noncross.begin(), noncross.end(), [](Interval x, Interval y){ return x.l < y.l; });
        for(auto &seg : noncross) {
            add[seg.l].push_back(&seg - &noncross[0]);
            rem[seg.r + 1].push_back(&seg - &noncross[0]);
        }
        int result = 0, cnt = 0;
        for(int pos = 1; pos <= 1000000; pos++) {
            if(add[pos].empty() && rem[pos].empty()) continue;
            for(int idx : add[pos]) active[idx] = true, cnt++;
            for(int idx : rem[pos]) active[idx] = false, cnt--;
            multiset<int> endpoints;
            int conflict = 0, ptr = 0;
            for(int i = 0; i < (int)noncross.size(); i++) if(active[i]) {
                while(ptr < (int)cross.size() && cross[ptr].l < noncross[i].l)
                    endpoints.insert(cross[ptr++].r);
                auto it = endpoints.upper_bound(noncross[i].r);
                if(it != endpoints.end()) conflict++, endpoints.erase(it);
            }
            result = max(result, cnt - conflict);
        }
        for(int i = 1; i <= 1000000; i++) add[i].clear(), rem[i].clear();
        cout << result + (int)cross.size() << '\n';
    }
    return 0;
}

Finding Cover Strings for Prefixes For a string s, a cover string t must appear such that every position in s is within at least one occurrence of t. The goal is to compute, for each prefix, the length of its shortest cover, with results XORed and processed online. Every cover of s is also a border of s. The set of covers forms a tree that is a subtree of the border tree. To find the maximal cover for each prefix, traverse the border tree. A key observation: any border longer than half the string length is a cover. This means on the border tree, only O(log n) edges may connect nodes where the border is not a cover. Using Link-Cut Trees (LCT) to track the last occurrence position of each border, one can binary search along chains of borders that are covers. This yields an O(n log² n) solution. An optimized approach leveraging the fact that large borders form arithmetic sequences (and thus chains in the tree) can achieve O(n log n) via tree decomposition without LCT.

#include <bits/stdc++.h>
struct LCTNode {
    int ch[2], par;
    bool isRoot(int x) { return ch[par][0]!=x && ch[par][1]!=x; }
    bool side(int x) { return ch[par][1]==x; }
    void link(int p, int c, bool d) { ch[p][d]=c; if(c) par=c; }
    void rotate(int x) {
        int p=par, g=par[p], d=side(x);
        if(!isRoot(p)) ch[g][side(p)]=x;
        par=x=g; link(p,ch[x][!d],d); link(x,p,!d);
    }
    void splay(int x) {
        while(!isRoot(x)) {
            if(!isRoot(par)) rotate(side(x)^side(par)?x:par);
            rotate(x);
        }
    }
    int access(int x) {
        int last=0;
        for(int y=x; y; y=par[last=y]) splay(y), ch[y][1]=last;
        return last;
    }
    void attach(int p, int c) {
        int r=access(p);
        while(ch[r][1]) r=ch[r][1];
        link(r,c,1); splay(c);
    }
    int furthest(int x) {
        splay(x);
        while(ch[x][1]) x=ch[x][1];
        splay(x);
        return x;
    }
} lct;
int main() {
    int n, mode; scanf("%d%d",&n,&mode);
    char str[n+2]; scanf("%s",str+1);
    int border[n+1]={0}, cover[n+1]={0}, chainTop[n+1]={0};
    int jump[n+1][20]={0}, prefixAns[n+1]={0};
    long long totalXor=0;
    auto validCover = [&](int i, int len) -> bool {
        return !len || (i - lct.furthest(len) <= len);
    };
    for(int i=1, j=0; i<=n; ++i) {
        if(mode) str[i] = (str[i] + prefixAns[i-1]) % 26 + 'a';
        if(i>1) {
            while(j && str[j+1]!=str[i]) j=border[j];
            if(str[j+1]==str[i]) ++j;
        }
        border[i]=jump[i][0]=j;
        for(int b=1; b<20; ++b) jump[i][b]=jump[jump[i][b-1]][b-1];
        int cur=border[i];
        while(chainTop[cur] && !validCover(i, chainTop[cur]))
            cur=border[chainTop[cur]];
        if(cur) {
            if(validCover(i,cur)) cover[i]=cur;
            else {
                for(int b=19; b>=0; --b)
                    if(jump[cur][b]>chainTop[cur] && !validCover(i, jump[cur][b]))
                        cur=jump[cur][b];
                cover[i]=border[cur];
            }
        }
        if(border[i]==cover[i] && cover[i]) chainTop[i]=chainTop[cover[i]];
        else chainTop[i]=i;
        prefixAns[i]=cover[i] ^ prefixAns[cover[i]];
        if(cover[i]) lct.attach(cover[i], i);
        totalXor += prefixAns[i];
    }
    printf("%lld\n", totalXor);
    return 0;
}

Selecting Paths for Maximum Common Overlap Given a weighted tree and a set of paths, select k paths to maximize the length of their common intersection. Consider a candidate node x as the deepest endpoint of the intersection. Paths with exactly one endpoint in x's subtree are relevant. Adding +1 to nodes on such paths and finding the farthest node from x with count ≥ k yields a candidate answer. Using DSU on tree, maintain a Fenwick tree per heavy path to support range updates. Two monotonic regions exist: ancestors of x have non-decreasing counts upwards, and descendants have non-decreasing counts downwards. Binary search on these segments using the Fenwick trees finds the farthest suitable node. Complexity is O(n log³ n).

#include <bits/stdc++.h>
using ll = long long;
std::vector<int> adj[200001], pathList[200001];
int parent[200001], depth[200001], heavy[200001], head[200001];
int tin[200001], tout[200001], timer=0;
ll dist[200001];
int pathU[230001], pathV[230001], pathLCA[230001];
struct BIT {
    std::vector<int> data; int sz;
    void init(int n) { data.assign(sz=n+1,0); }
    void update(int i, int d) { for(; i<=sz; i+=i&-i) data[i]+=d; }
    int query(int i) { int s=0; for(; i>0; i-=i&-i) s+=data[i]; return s; }
    int findKth(int k) {
        int idx=0, bit=1<<(31-__builtin_clz(sz));
        for(; bit; bit>>=1) if(idx+bit<=sz && data[idx+bit]<k) k-=data[idx+=bit];
        return idx+1;
    }
} bit[200001];
int lca(int u, int v) {
    while(head[u]!=head[v]) {
        if(depth[head[u]] < depth[head[v]]) std::swap(u,v);
        u = parent[head[u]];
    }
    return depth[u] < depth[v] ? u : v;
}
void dfsHeavy(int u, int p) {
    parent[u]=p; heavy[u]=-1; int maxSub=0;
    for(int v : adj[u]) if(v!=p) {
        depth[v]=depth[u]+1;
        dfsHeavy(v, u);
        if(subtreeSize[v] > maxSub) maxSub=subtreeSize[v], heavy[u]=v;
    }
}
void dfsDecompose(int u, int h) {
    head[u]=h; tin[u]=++timer;
    if(heavy[u] != -1) dfsDecompose(heavy[u], h);
    for(int v : adj[u]) if(v!=parent[u] && v!=heavy[u]) dfsDecompose(v, v);
    tout[u]=timer;
}
ll bestLen=0; int bestU, bestV;
void updateBest(int u, int v, int w) {
    ll d = dist[u]+dist[v]-2*dist[w];
    if(d > bestLen || (d==bestLen && (u<bestU || (u==bestU && v<bestV))))
        bestLen=d, bestU=u, bestV=v;
}
int activePathEnd[230001];
std::vector<int> modifiedChains;
void modifyChain(int x, int y, int delta) {
    while(true) {
        int h = head[x];
        int pos = depth[x] - depth[h];
        bit[h].update(pos+1, delta);
        if(h == head[y]) {
            bit[h].update(depth[y]-depth[h]+2, -delta);
            break;
        }
        x = parent[h];
    }
}
void processSubtree(int u, bool clear) {
    for(int v : adj[u]) if(v!=parent[u] && v!=heavy[u]) processSubtree(v, true);
    if(heavy[u]!=-1) processSubtree(heavy[u], false);
    for(int v : adj[u]) if(v!=parent[u] && v!=heavy[u]) {
        for(int pid : pathList[v]) {
            int other = pathU[pid] ^ pathV[pid] ^ v;
            if(activePathEnd[pid]) modifyChain(activePathEnd[pid], pathLCA[pid], -1);
            modifyChain(activePathEnd[pid]=other, pathLCA[pid], 1);
        }
    }
    for(int pid : pathList[u]) {
        int other = pathU[pid] ^ pathV[pid] ^ u;
        if(activePathEnd[pid]) modifyChain(activePathEnd[pid], pathLCA[pid], -1);
        modifyChain(activePathEnd[pid]=other, pathLCA[pid], 1);
    }
    int candidate = u;
    for(int b=17; b>=0; --b) {
        int anc = parent[candidate];
        if(anc && bit[head[anc]].query(depth[anc]-depth[head[anc]]+1) >= k)
            candidate = anc;
    }
    if(candidate != u) updateBest(u, candidate, candidate);
    if(clear) {
        for(int pid : pathList[u]) {
            if(activePathEnd[pid]) {
                modifyChain(activePathEnd[pid], pathLCA[pid], -1);
                activePathEnd[pid]=0;
            }
        }
    }
}
int main() {
    int n, m; scanf("%d%d%d",&n,&m,&k);
    for(int i=1; i<n; i++) {
        int a,b,w; scanf("%d%d%d",&a,&b,&w);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfsHeavy(1,0); dfsDecompose(1,1);
    for(int i=1; i<=n; i++) if(head[i]==i) bit[i].init(depth[i]-depth[head[i]]+1);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&pathU[i],&pathV[i]);
        pathLCA[i] = lca(pathU[i], pathV[i]);
        pathList[pathU[i]].push_back(i);
        pathList[pathV[i]].push_back(i);
    }
    processSubtree(1, true);
    printf("%lld\n%d %d\n", bestLen, bestU, bestV);
}