46672023-03-30 18:51:29gortomiLegkisebb nem oszthatócpp17Runtime error 0/1001.508s43472 KiB
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
int tim = 0;
vector<int> l, r, par;
void dfs(int n, int p)
{
    par[n] = p;
    l[n] = tim++;
    for(auto x : g[n]) if(x != p) dfs(x, n);
    r[n] = tim++;
}
struct val
{
    int l, r, ind, ty;
};
bool comp(val a, val b)
{
    return a.l / 350 < b.l / 350 || (a.l / 350 == b.l / 350 && a.r < b.r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> prim;
    vector<bool> ip(1e6 + 1, 1);
    vector<int> pl(1e6 + 1);
    g.resize(n + 1);
    l.resize(n + 1);
    r.resize(n + 1);
    par.resize(n + 1);
    for(int i = 2; i <= 1e6; i++)
    {
        if(ip[i])
        {
            pl[i] = prim.size();
            prim.push_back(i);
            for(int j = 2 * i; j <= 1e6; j += i)
            {
                ip[j] = 0;
            }
        }
    }
    vector<int> v(n + 1, 1e6 + 1);
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if(ip[x]) v[i] = pl[x];
    }
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    vector<int> path(2 * n);
    for(int i = 1; i <= n; i++)
    {
        path[l[i]] = i;
        path[r[i]] = i;
    }
    int q;
    cin >> q;
    vector<val> que(q + 1);
    que[0] = {0, -1, 0};
    vector<int> ans(q);
    for(int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        if(l[x] < l[y] && r[x] < r[y])
        {
            que[i].l = r[x];
            que[i].r = l[y];
            que[i].ty = 1;
        }
        else if(l[x] > l[y] && r[x] > r[y])
        {
            que[i].l = r[y];
            que[i].r = l[x];
            que[i].ty = 1;
        }
        else
        {
            que[i].l = l[x];
            que[i].r = l[y];
            if(que[i].l > que[i].r) swap(que[i].l, que[i].r);
            que[i].ty = 0;
        }
        que[i].ind = i - 1;
    }
    sort(que.begin(), que.end(), comp);
    const int b = 350;
    vector<int> sq(b);
    vector<int> db(n + 1);
    vector<bool> act(n + 1);
    for(int i = 1; i <= q; i++)
    {
        for(int j = que[i - 1].l - 1; j >= que[i].l; j--)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = que[i - 1].r + 1; j <= que[i].r; j++)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = que[i - 1].l; j <= que[i].l - 1; j++)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        for(int j = que[i - 1].r; j >= que[i].r + 1; j--)
        {
            int y = path[j];
            int x = v[y];
            if(x > n) continue;
            if(!act[y])
            {
                act[y] = 1;
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
            else
            {
                act[y] = 0;
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
        if(que[i].ty == 1)
        {
            int x = v[par[que[i].l]];
            if(x <= n)
            {
                db[x]++;
                if(db[x] == 1) sq[x / b]++;
            }
        }
        for(int j = 0; j < b; j++)
        {
            if(sq[j] < b)
            {
                for(int k = 0; k < b; k++)
                {
                    if(db[j * b + k] == 0)
                    {
                        ans[que[i].ind] = j * b + k;
                        break;
                    }
                }
                break;
            }
        }
        if(que[i].ty == 1)
        {
            int x = v[par[que[i].l]];
            if(x <= n)
            {
                db[x]--;
                if(db[x] == 0) sq[x / b]--;
            }
        }
    }
    for(auto x : ans) cout << prim[x] << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted19ms11076 KiB
subtask20/5
2Accepted20ms11288 KiB
3Accepted19ms11508 KiB
4Runtime error20ms11724 KiB
5Runtime error20ms11700 KiB
6Runtime error20ms12068 KiB
7Accepted21ms12160 KiB
8Accepted21ms12356 KiB
9Accepted20ms12444 KiB
10Accepted21ms12528 KiB
11Runtime error21ms12656 KiB
subtask30/5
12Accepted19ms12904 KiB
13Wrong answer19ms12872 KiB
14Runtime error20ms12724 KiB
15Runtime error20ms12844 KiB
16Runtime error20ms12840 KiB
17Runtime error20ms12980 KiB
18Runtime error20ms12984 KiB
19Runtime error20ms13068 KiB
20Runtime error23ms13328 KiB
21Runtime error21ms13196 KiB
subtask40/10
22Runtime error34ms15336 KiB
23Accepted128ms19656 KiB
24Accepted200ms28456 KiB
25Accepted291ms35452 KiB
26Accepted335ms39876 KiB
27Accepted344ms39312 KiB
subtask50/10
28Runtime error43ms15260 KiB
29Runtime error126ms19152 KiB
30Wrong answer564ms26156 KiB
31Wrong answer1.19s31584 KiB
32Wrong answer1.508s33752 KiB
33Wrong answer1.506s33752 KiB
subtask60/10
34Runtime error20ms13832 KiB
35Accepted34ms15820 KiB
36Runtime error67ms20780 KiB
37Accepted158ms29472 KiB
38Accepted228ms37780 KiB
39Accepted256ms38592 KiB
40Accepted259ms42108 KiB
41Accepted270ms38952 KiB
subtask70/15
42Runtime error21ms13964 KiB
43Runtime error34ms15708 KiB
44Runtime error82ms19884 KiB
45Wrong answer250ms26640 KiB
46Wrong answer456ms32356 KiB
47Wrong answer551ms34164 KiB
48Wrong answer551ms34208 KiB
49Wrong answer541ms34112 KiB
50Wrong answer596ms34328 KiB
51Wrong answer128ms38060 KiB
52Accepted162ms30828 KiB
53Accepted159ms36804 KiB
54Wrong answer128ms38220 KiB
55Accepted160ms30832 KiB
56Wrong answer1.105s30836 KiB
subtask80/20
57Accepted35ms16404 KiB
58Runtime error65ms21440 KiB
59Wrong answer149ms25856 KiB
60Accepted252ms31600 KiB
61Wrong answer259ms40708 KiB
62Accepted259ms42920 KiB
63Accepted375ms39752 KiB
64Accepted337ms40400 KiB
65Accepted175ms43472 KiB
66Accepted171ms43464 KiB
subtask90/25
67Runtime error39ms16112 KiB
68Runtime error75ms19612 KiB
69Wrong answer193ms23456 KiB
70Wrong answer619ms27152 KiB
71Wrong answer532ms34228 KiB
72Wrong answer550ms34520 KiB
73Wrong answer1.172s34500 KiB
74Wrong answer813ms34500 KiB
75Wrong answer669ms34392 KiB
76Wrong answer832ms34428 KiB
77Wrong answer902ms34464 KiB
78Wrong answer745ms34380 KiB
79Wrong answer915ms34392 KiB
80Accepted367ms38072 KiB
81Accepted400ms38036 KiB
82Accepted168ms43364 KiB
83Wrong answer847ms39204 KiB