题意（CodeForces 588E）

给定一棵\(n\)个点的树，给定\(m\)个人（\(m\le n\)）在哪个点上的信息，每个点可以有任意个人；然后给\(q\)个询问，每次问\(u\)到\(v\)上的路径有的点上编号最小的\(k(k \le 10)\)个人（没有那么多人就该有多少人输出多少人）。

分析

\(u\)到\(v\)上路径的询问很显然的想到LCA，但是要维护前\(k\)个在路径上的最小的点似乎是个有点麻烦的问题。其实，找到了LCA（设为\(p\)点），我们就可以同样的利用倍增的思想把\(u\)到\(p\)与\(v\)到\(p\)点的路径上的人全部求出（这里有个小技巧，对于\(u\)和\(v\)点不妨错开一层求，这样可以避免去重的问题）。然后就是前\(k\)大了，这里网上有的题解比较牛逼，起手一个主席树，本数据结构废物并不会，所以学习了一下CF的题解，采用了一种比较简单的方法来处理（注意到\(k\)最大值不超过10）。

代码

经典的倍增在线求LCA板子。

#include <bits/stdc++.h>

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x,0,sizeof(x))

#define MS(x,y) memset(x,y,sizeof(x))

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef ll repType;

const int MAXN=100005;

const int MAXD=18;

vector<int> G[MAXN];

struct Node

{

    int a[11];

    Node() { MS(a, 63); }

    void

    insert(int x)

	{

        a[10]=x;

        sort(a, a+11);

    }

} vals[MAXD][MAXN];

Node

merge_node(const Node& x, const Node& y)

{

    Node ans=x;

    rep(i, 0, 10) { ans.insert(y.a[i]); }

    return ans;

}

int fa[MAXD][MAXN], d[MAXN];

void

dfs(int pre, int now)

{

    fa[0][now]=pre;

    rep(i, 1, MAXD-1)

    {

        fa[i][now]=fa[i-1][fa[i-1][now]];

        vals[i][now]=merge_node(vals[i-1][now], vals[i-1][fa[i-1][now]]);

    }

    rep(i, 0, int(G[now].size())-1)

    {

        int v=G[now][i];

        if(v!=pre)

        {

            d[v]=d[now]+1;

            dfs(now, v);

        }

    }

}

inline int

get_fa(int v, int k) // k=1, it will points to v _itself_.

{

    rep(i, 0, MAXD-1)

		if((1<<i) & k)

		    { v=fa[i][v]; }

    return v;

}

int

LCA(int u, int v)

{

    if(d[u]<d[v]) { swap(u, v); }

    u=get_fa(u, d[u]-d[v]);

	if(u==v) { return u; }

    else per(i, MAXD-1, 0)

	{

		if(fa[i][u]!=fa[i][v])

		{

			u=fa[i][u];

			v=fa[i][v];

		}

	}

    return fa[0][v];

}

inline Node

get_people(int v, int k)

{

    Node ans;

    rep(i, 0, MAXD-1)

        if((1<<i) & k)

        {

            ans=merge_node(ans, vals[i][v]);

            v=fa[i][v];

        }

    return ans;

}

int

main()

{

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    int n, m, q; cin>>n>>m>>q;

    rep(i, 1, n-1)

    {

        int u, v; cin>>u>>v;

        G[u].PB(v); G[v].PB(u);

    }

    rep(i, 1, m)

    {

        int c; cin>>c;

        vals[0][c].insert(i);

    }

    dfs(1, 1);

    rep(i, 1, q)

    {

        int u, v, k; cin>>u>>v>>k;

        int p=LCA(u, v);

        Node x=get_people(u, d[u]-d[p]); // it will get the point _below_ the LCA.

        Node y=get_people(v, d[v]-d[p]+1); // it will go through another route,

        Node ans=merge_node(x, y);         // if not, y _itself_ must be the LCA,

        int tmp=0;                         // and the y will be the value of V.

        while(tmp<k && ans.a[tmp]<=m) { tmp++; }

        k=tmp;

        cout<<k;

        rep(i, 0, k-1) cout<<" "<<ans.a[i];

        cout<<endl;

    }

    return 0;

}

巴特西

「日常训练」Duff in the Army （Codeforces Round #326 Div.2 E）

题意（CodeForces 588E）

分析

代码

最新文章

热门文章