Размер программы

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
vector <int> odd_manacher(string s) {
    int n = (int) s.size();
    vector <int> d(n);
    int l = 0, r = -1;
    for (int i = 0; i < n; i++) {
        int k = 0;
        if (i <= r) {
            int pos = r - i;
            k = min(d[l + pos], r - i);
        }
        while (i - (k + 1) >= 0 && i + (k + 1) < n && s[i - (k + 1)] == s[i + (k + 1)]) {
            k++;
        }
        d[i] = k;
        if (i + d[i] > r) {
            l = i - d[i], r = i + d[i];
        }
    }
    return d;
}
 
vector <int> even_manacher(string s) {
    int n = (int) s.size();
    vector <int> d(n);
    int l = 0, r = -1;
    for (int i = 0; i < n; i++) {
        if (i <= r) {
            int pos = r - i;
            d[i] = min(d[l + pos], r - i);
        }
        int k = d[i];
        while (i - (k + 1) >= 0 && i + k < n && s[i - (k + 1)] == s[i + k]) {
            k++;
        }
        d[i] = k;
        if (d[i] && i + d[i] - 1 > r) {
            l = i - d[i], r = i + d[i] - 1;
        }
    }
    return d;
}
 
const int N = 5e5;
 
vector <pair <int, int> > add[N];
int fenw[2][N];
 
void inc(int t, int x, int y) {
    for (; x < N; x = (x | (x + 1))) {
        fenw[t][x] += y;
    }
}
 
int get(int t, int x) {
    int s = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1) {
        s += fenw[t][x];
    }
    return s;
}
 
ll get_sum(int t, int l, int r) {
    return get(t, r) - get(t, l - 1);
}
 
ll solve_odd(string s) {
    vector <int> d = odd_manacher(s);
    int n = (int) s.size();
    for (int i = 0; i <= n; i++) {
        add[i].clear();
    }
    auto add_segm = [&] (int l, int r, int who) {
        r = min(r, n - 1);
        add[l].push_back({who, 1});
        add[r + 1].push_back({who, -1});
    };
    for (int i = 0; i < n; i++) {
        add_segm(i + 1, i + d[i] * 2 + 1, i);
    }
    ll ans = 0;
    for (int i = 0; i <= n; i++) {
        for (auto c : add[i]) {
            inc(c.first % 2, c.first, c.second);
        }
        if (i < n) {
            ans += get_sum((i + 1) % 2, i - d[i] * 2 - 1, i - 1);
        }
    }
    return ans;
}
 
ll solve_even(string s) {
    vector <int> d = even_manacher(s);
    int n = (int) s.size();
    for (int i = 0; i <= n; i++) {
        add[i].clear();
    }
    auto add_segm = [&] (int l, int r, int who) {
        r = min(r, n - 1);
        add[l].push_back({who, 1});
        add[r + 1].push_back({who, -1});
    };
    for (int i = 0; i < n; i++) {
        add_segm(i + 1, i + d[i] * 2, i);
    }
     ll ans = 0;
    for (int i = 0; i <= n; i++) {
        for (auto c : add[i]) {
            inc(c.first % 2, c.first, c.second);
        }
        if (i < n) {
            ans += get_sum(i % 2, i - d[i] * 2, i - 1);
        }
    }
    return ans;
}
 
int main() {
#ifdef iq
    freopen("a.in", "r", stdin);
#endif // iq
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    cout << solve_odd(s) + solve_even(s) << endl;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define debug(x) cerr << #x << ": " << x << endl
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double dbl;
 
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; };
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; };
 
void die()
{
    cout << "-1\n";
    exit(0);
}
 
int V;
 
int n, m, TASK;
const int maxN = 500005;
const int logN = 19;
vector<int> G[maxN];
pii path[maxN];
int depth[maxN];
int up[logN][maxN];
int par[maxN];
int tin[maxN];
int tout[maxN];
map<pii, int> ed;
pii edge[maxN];
 
vector<pii> H[maxN];
int col[maxN];
int C[maxN];
 
int timer;
void dfs1(int v, int p = -1, int h = 0)
{
    tin[v] = timer++;
    par[v] = p;
    up[0][v] = par[v];
    for (int j = 1; j < logN && up[j - 1][v] != -1; ++j)
        up[j][v] = up[j - 1][up[j - 1][v]];
    for (int u : G[v])
        if (u != p)
            dfs1(u, v, h + 1);
    tout[v] = timer - 1;
}
 
bool upper(int a, int b)
{
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}
 
int lca(int a, int b)
{
    if (a == b) return a;
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int j = logN - 1; j >= 0; --j)
        if (up[j][a] != -1 && !upper(up[j][a], b))
            a = up[j][a];
    return par[a];
}
 
vector<int> st;
void dfs_find(int v, int b, int p, vector<int> &q)
{
    st.push_back(v);
    if (v == b)
        q = vector<int>(all(st));
    else
        for (int u : G[v])
            if (u != p)
                dfs_find(u, b, v, q);
    st.pop_back();
}
 
bool cfs(int v, int c = 0)
{
    col[v] = c;
    for (pii p : H[v])
    {
        int u = p.fi;
        int dc = p.se;
        if (col[u] == -1)
        {
            if (!cfs(u, c ^ dc))
            {
                return false;
            }
        }
        else if (col[u] != (col[v] ^ dc))
        {
            return false;
        }
    }        
    return true;
}
 
void dfs2(int v)
{
    int mx = 0;
    for (int u : G[v])
    {
        int i = ed[mp(v, u)];
        if ((col[i] == 0) == (v == edge[i].fi && u == edge[i].se))
        {
            if (C[u] == -1)
                dfs2(u);
            chkmax(mx, C[u]);
        }
    }
    C[v] = mx + 1;
}
 
void print_ans()
{
    memset(C, 255, sizeof(C));
    for (int v = 1; v <= n; ++v)
        if (C[v] == -1)
            dfs2(v);
    cout << *max_element(C + 1, C + n + 1) << '\n';
    for (int v = 1; v <= n; ++v)
    {
        cout << C[v] << ' ';
    }
    cout << '\n';
}
 
bool dp[2][102][102][102];
bool has_up[2][102][102];
bool has_down[2][102][102];
bool inh[102];
int cl[102];
int cl2[102];
 
void dfs4(int v)
{
    for (int u : G[v])
        if (u != par[v])
            dfs4(u);
    //
    vector<int> edges;
    for (int u : G[v])
    {
        int i = ed[mp(u, v)];
        edges.pb(i);
        inh[i] = true;
    }
 
    for (int prot = 0; prot < 2; ++prot)
    {
        for (int max_up = 0; max_up <= n; ++max_up)
        {
            for (int max_down = 0; max_down <= n; ++max_down)
            {
                if (max_up + max_down > V)
                {
                    continue;
                }
                function< bool(int, int) > zhfs = [&](int e, int c) -> bool
                {
                    cl[e] = c;
                    int w = edge[e].fi;
                    if (w == v)
                        w = edge[e].se;
                    if (w != par[v])
                    {
                        if (c == 0)
                        {
                            // down
                            if (!has_down[0][w][max_down - 1])
                            {
                                return false;
                            }
                        }
                        else
                        {
                            // up
                            if (!has_up[1][w][max_up - 1])
                            {
                                return false;
                            }
                        }
                    }
                    for (pii pr : H[e])
                    {
                        int e2 = pr.first;
                        int dc = pr.second;
                        if (inh[e2] && cl[e2] == -1)
                        {
                            if (!zhfs(e2, c ^ dc))
                            {
                                return false;
                            }
                        }
                    }
                    return true;
                };
                function< bool(int, int) > zhfs2 = [&](int e, int c) -> bool
                {
                    cl2[e] = c;
                    int w = edge[e].fi;
                    if (w == v)
                        w = edge[e].se;
                    if (w != par[v])
                    {
                        if (c == 0)
                        {
                            // down
                            if (!has_down[0][w][max_down - 1])
                            {
                                return false;
                            }
                        }
                        else
                        {
                            // up
                            if (!has_up[1][w][max_up - 1])
                            {
                                return false;
                            }
                        }
                    }
                    for (pii pr : H[e])
                    {
                        int e2 = pr.first;
                        int dc = pr.second;
                        if (inh[e2] && cl2[e2] == -1)
                        {
                            if (!zhfs(e2, c ^ dc))
                            {
                                return false;
                            }
                        }
                    }
                    return true;
                };
                for (int e : edges)
                {
                    cl[e] = cl2[e] = -1;
                }
                auto &fl = dp[prot][v][max_up][max_down];
                fl = 1;
                if (par[v] != -1)
                {
                    fl &= zhfs(ed[mp(par[v], v)], prot);
                }
 
                for (int e : edges)
                {
                    if (cl[e] == -1)
                    {
                        if (zhfs2(e, 0))
                        {
                            fl &= zhfs(e, 0);
                        }
                        else
                        {
                            fl &= zhfs(e, 1);
                        }
                    }
                }
 
                if (fl)
                {
                    has_up[prot][v][max_down] = true;
                    has_up[prot][v][max_up] = true;
                }
            }
        }
        if (par[v] == -1)
        {
            break;
        }
    }
 
    for (int e : edges)
        inh[e] = false;
}
 
void restore(int prot, int v, int max_up, int max_down)
{
    vector<int> edges;
    for (int u : G[v])
    {
        int i = ed[mp(u, v)];
        edges.pb(i);
        inh[i] = true;
    }
 
                function< bool(int, int) > zhfs = [&](int e, int c) -> bool
                {
                    cl[e] = c;
                    int w = edge[e].fi;
                    if (w == v)
                        w = edge[e].se;
                    if (w != par[v])
                    {
                        if (c == 0)
                        {
                            // down
                            if (!has_down[0][w][max_down - 1])
                            {
                                return false;
                            }
                        }
                        else
                        {
                            // up
                            if (!has_up[1][w][max_up - 1])
                            {
                                return false;
                            }
                        }
                    }
                    for (pii pr : H[e])
                    {
                        int e2 = pr.first;
                        int dc = pr.second;
                        if (inh[e2] && cl[e2] == -1)
                        {
                            if (!zhfs(e2, c ^ dc))
                            {
                                return false;
                            }
                        }
                    }
                    return true;
                };
                function< bool(int, int) > zhfs2 = [&](int e, int c) -> bool
                {
                    cl2[e] = c;
                    int w = edge[e].fi;
                    if (w == v)
                        w = edge[e].se;
                    if (w != par[v])
                    {
                        if (c == 0)
                        {
                            // down
                            if (!has_down[0][w][max_down - 1])
                            {
                                return false;
                            }
                        }
                        else
                        {
                            // up
                            if (!has_up[1][w][max_up - 1])
                            {
                                return false;
                            }
                        }
                    }
                    for (pii pr : H[e])
                    {
                        int e2 = pr.first;
                        int dc = pr.second;
                        if (inh[e2] && cl2[e2] == -1)
                        {
                            if (!zhfs(e2, c ^ dc))
                            {
                                return false;
                            }
                        }
                    }
                    return true;
                };
                for (int e : edges)
                {
                    cl[e] = cl2[e] = -1;
                }
                auto &fl = dp[prot][v][max_up][max_down];
                fl = 1;
                if (par[v] != -1)
                {
                    fl &= zhfs(ed[mp(par[v], v)], prot);
                }
 
                for (int e : edges)
                {
                    if (cl[e] == -1)
                    {
                        if (zhfs2(e, 0))
                        {
                            fl &= zhfs(e, 0);
                        }
                        else
                        {
                            fl &= zhfs(e, 1);
                        }
                    }
                }
 
                if (fl)
                {
                    has_up[prot][v][max_down] = true;
                    has_up[prot][v][max_up] = true;
                }
 
    for (int e : edges)
        inh[e] = false;
}
 
signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    memset(up, 255, sizeof(up));
 
    cin >> n >> m >> TASK;
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
        ed[mp(a, b)] = ed[mp(b, a)] = i;
        edge[i] = {a, b};
    }
    vector<int> _cnt(n + 1, 0);
    for (int j = 0; j < m; ++j)
    {
        cin >> path[j].fi >> path[j].se;
        _cnt[path[j].fi]++;
        _cnt[path[j].se]++;
    }
 
    int root = 1;
    bool found = false;
    for (int v = 1; v <= n; ++v)
    {
        if (_cnt[v] == m)
        {
            found = true;
            root = v;
            break;
        }
    }
 
    dfs1(root);
    for (int i = 0; i < n - 1; ++i)
    {
        if (par[edge[i].fi] == edge[i].se)
        {
            swap(edge[i].fi, edge[i].se);
        }
    }
 
    if (false && n <= 100 && m <= 100)
    {
        for (int j = 0; j < m; ++j)
        {
            int a = path[j].fi;
            int b = path[j].se;
            vector<int> p;
            int c = lca(a, b);
            for (; a != c; a = par[a])
                p.push_back(a);
            p.push_back(c);
            int sz = p.size();
            for (; b != c; b = par[b])
                p.push_back(b);
            reverse(p.begin() + sz, p.end());
            for (int i = 0; i + 2 < p.size(); ++i)
            {
                int x = p[i];
                int y = p[i + 1];
                int z = p[i + 2];
                int e1 = ed[mp(x, y)];
                int e2 = ed[mp(y, z)];
                int dc = 0;
                if (par[y] != x && par[y] != z)
                {
                    dc = 1;
                }
                H[e1].emplace_back(e2, dc);
                H[e2].emplace_back(e1, dc);
            }
        }
        memset(col, 255, sizeof(col));
        for (int i = 0; i < n - 1; ++i)
            if (col[i] == -1)
                if (!cfs(i))
                    die();
        //
        int vl = 0;
        int vr = n;
        while (vr - vl > 1)
        {
            memset(dp, 0, sizeof(dp));
            V = (vl + vr) >> 1;
            dfs4(root);
            bool found = false;
            for (int max_up = 0; max_up <= n; ++max_up)
            {
                for (int max_down = 0; max_down <= n; ++max_down)
                {
                    if (dp[0][root][max_up][max_down] && max_up + max_down <= V)
                    {
                        found = true;
                        break;
                    }
                }
            }
            if (found)
                vl = V;
            else
                vr = V;
        }
        V = vl;
        memset(dp, 0, sizeof(dp));
        dfs4(root);
        for (int max_up = 0; max_up <= n; ++max_up)
            {
                for (int max_down = 0; max_down <= n; ++max_down)
                {
                    if (dp[0][root][max_up][max_down] && max_up + max_down <= V)
                    {
                        restore(0, root, max_up, max_down);
                        memcpy(col, cl, sizeof(cl));
                        print_ans();
                        exit(0);
                    }
                }
            }
    }
 
    if (TASK == 0)
    {
        for (int j = 0; j < m; ++j)
        {
            int a = path[j].fi;
            int b = path[j].se;
            vector<int> p;
            int c = lca(a, b);
            for (; a != c; a = par[a])
                p.push_back(a);
            p.push_back(c);
            int sz = p.size();
            for (; b != c; b = par[b])
                p.push_back(b);
            reverse(p.begin() + sz, p.end());
            for (int i = 0; i + 2 < p.size(); ++i)
            {
                int x = p[i];
                int y = p[i + 1];
                int z = p[i + 2];
                int e1 = ed[mp(x, y)];
                int e2 = ed[mp(y, z)];
                int dc = 0;
                if (par[y] != x && par[y] != z)
                {
                    dc = 1;
                }
                H[e1].emplace_back(e2, dc);
                H[e2].emplace_back(e1, dc);
            }
        }
        memset(col, 255, sizeof(col));
        for (int i = 0; i < n - 1; ++i)
            if (col[i] == -1)
                if (!cfs(i))
                    die();
        print_ans();
        exit(0);
    }
 
    return 0;
}