省选连结T1RMQ+欧拉序样例没过求调

常规
1

用 RMQ+欧拉序做。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
struct edge
{
    int nxt,to;
}e[maxn << 1];
int head[maxn],tot;
void add_edge(int u,int v)
{
    e[++tot].nxt = head[u];
    head[u] = tot;
    e[tot].to = v;
}
int dfn[maxn << 1],pos[maxn],st[maxn << 1][30],rev[maxn < 1][30];
int dep[maxn],cnt;
int lg[maxn];

void dfs(int u,int Dep)
{
    dfn[++cnt] = u;
    dep[cnt] = Dep;
    pos[u] = cnt;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(pos[v])continue;
        dfs(v,Dep + 1);
        dfn[++cnt] = u;
        dep[cnt]  = Dep;
    }
}

void init()
{
    for(int i = 2;i <= cnt + 1;i++)
    {
        lg[i] = lg[i >> 1] + 1;
    }
    for(int i = 1;i <= cnt;i++)
    {
        st[i][0] = dep[i];
        rev[i][0] = dfn[i];
    }
    for(int i = 1;i <= lg[cnt];i++)
    {
        for(int j = 1;j + (1 << i) - 1 <= cnt;j++)
        {
            if(st[j][i - 1] < st[j + (1 << i - 1)][i])
            {
                st[j][i] = st[j][i - 1];
                rev[j][i] = rev[j][i - 1];
            }
            else
            {
                st[j][i] = st[j + (1 << i - 1)][i - 1];
                rev[j][i] = rev[j + (1 << i - 1)][i - 1];
            }
        }
    }
}

int query(int l,int r)
{
    int k = lg[r - l + 1];
    return st[l][k] < st[r + 1 - (1 << k)][k] ? rev[l][k] : rev[r + 1 - (1 << k)][k];
}

int n,m;
unsigned int  seed;

namespace mtr {
  std::mt19937 get;
  void init(unsigned int seed) {
    get.seed(seed);
  }
}
int main()
{
    cin >> n >> m;
    for(int i = 2;i <= n;i++)
    {
        int u;
        cin >> u;
        add_edge(u,i);
        add_edge(i,u);
    }
    dfs(1,0);
    init();
    cin >> seed;
    int ans = 0;
    mtr::init(seed);
    for (int i = 1;i <= m;i++)
    {
        int x = mtr::get() % n + 1;
        int y = mtr::get() % n + 1;
        ans += i * query(x,y);
    }
    cout << ans;
    return 0;
}
2 个赞
2

样例把每组xy输出出来看看lca弄没弄对 ，虽然是随机种子还是可以拿错误数据debug的

2 个赞
3 
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
struct edge
{
    int nxt,to;
}e[maxn << 1];
int head[maxn],tot;
void add_edge(int u,int v)
{
    e[++tot].nxt = head[u];
    head[u] = tot;
    e[tot].to = v;
}
int dfn[maxn << 1],pos[maxn],st[30][maxn << 1],rev[30][maxn << 1];
int dep[maxn],cnt;
int lg[maxn];

void dfs(int u,int Dep)
{
    dfn[++cnt] = u;
    dep[cnt] = Dep;
    pos[u] = cnt;
    for(int i = head[u];i;i = e[i].nxt)
    {
        int v = e[i].to;
        if(pos[v])continue;
        dfs(v,Dep + 1);
        dfn[++cnt] = u;
        dep[cnt] = Dep;
    }
}

void init()
{
    for(int i = 2;i <= cnt + 1;i++)
    {
        lg[i] = lg[i >> 1] + 1;
    }
    for(int i = 1;i <= cnt;i++)
    {
        st[0][i] = dep[i];
        rev[0][i] = dfn[i];
    }
    for(int i = 1;i <= lg[cnt];i++)
    {
        for(int j = 1;j + (1 << i) - 1 <= cnt;j++)
        {
            if(st[i - 1][j] < st[i - 1][j + (1 << i - 1)])
            {
                st[i][j] = st[i - 1][j];
                rev[i][j] = rev[i - 1][j];
            }
            else
            {
                st[i][j] = st[i - 1][j + (1 << i - 1)];
                rev[i][j] = rev[i - 1][j + (1 << i - 1)];
            }
        }
    }
}

int query(int l,int r)
{
    int k = lg[r - l + 1];
    return st[k][l] < st[k][r - (1 << k)] ? rev[k][l] : rev[k][r + 1 - (1 << k)];
}

int n,m;
unsigned int seed;

namespace mtr {
  std::mt19937 get;
  void init(unsigned int seed) {
    get.seed(seed);
  }
}
signed main()
{
    cin >> n >> m;
    for(int i = 2;i <= n;i++)
    {
        int u;
        cin >> u;
        add_edge(u,i);
        add_edge(i,u);
    }
    dfs(1,1);
    init();
    cin >> seed;
    int ans = 0;
    mtr::init(seed);
    for (int i = 1;i <= m;i++)
    {
        int x = mtr::get() % n + 1;
        int y = mtr::get() % n + 1;
        if(pos[x] > pos[y])swap(x,y);
        ans = (i * query(pos[x],pos[y]) % mod + ans) % mod;
    }
    cout << ans;
    return 0;
}

现在成WA0了

2 个赞
4

query写错了是st[k][l]<sr[k][r + 1 - (1 << k)] 不是 st[k][l]<sr[k][r - (1 << k)]

2 个赞
5

膜拜大佬