【Henu ACM Round#15 E】 A and B and Lecture Rooms

【链接】我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

最近公共祖先。
(树上倍增

一开始统计出每个子树的节点个数_size[i]

如果x和y相同。

那么直接输出n.

否则求出x和y的最近公共祖先。z

(假定y的深度大于x

【1】如果z等于x或y中的一个。

那么久就找到x..y的路径(长度设为L)中的中点u。

显然,u和它的其他len-1个子树上的任意一个节点都是可行的(除了那个包含y的子树

设_get(x,step)表示x节点往上走step步到达的节点

则输出_sum[中点]-_sum[ _get(y,L/2) ]即可

【2】如果z不等于x和y中的任意一个。

①x和y往上走的距离是一样的。

->那么z的子树中,除了这两个节点往上走上来的子树,

其他子树里面的节点都是可行的

②x和y往上走的距离不一样。

->那么就还是和【1】中的情况一样,找出中点即可。

_get(x,step)函数可以用树上倍增的p数组实现。

【代码】

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+10;

const int MAX = 17;

vector <int> son[MAXN],g[MAXN];

int n,p[MAXN][MAX+5],dep[MAXN],pre[MAX+5],m;

int _size[MAXN];

void dfs(int x,int f)

{

    _size[x] = 1;

    dep[x] = dep[f] + 1;

    p[x][0] = f;

    for (int i = 1; i <= MAX; i++) p[x][i] = p[p[x][i - 1]][i - 1];

    int len = g[x].size();

    for (int i = 0; i <= len - 1; i++)

    {

        int y = g[x][i];

        if (y != f) {

            son[x].push_back(y);

            dfs(y, x);

            _size[x]+=_size[y];

        }

    }

}

int _get(int x,int ma){

    for (int i = MAX;i>=0;i--){

        if (ma>=pre[i]){

            ma-=pre[i];

            x = p[x][i];

        }

    }

    return x;

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0);

    #ifdef LOCAL_DEFINE

        freopen("rush.txt","r",stdin);

    #endif

    pre[0] = 1;

    for (int i = 1; i <= MAX; i++)

        pre[i] = pre[i - 1] << 1;

    cin >> n;

    for (int i = 1; i <= n; i++)

        son[i].clear();

    for (int i = 1; i <= n - 1; i++)

    {

        int x, y;

        cin >> x >> y;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    dfs(1, 0);

    cin >> m;

    for (int i = 1; i <= m; i++)

    {

        int t0, t1,pret1,pret0;

        cin >> t0 >> t1;

        if(t0==t1){

            cout<<n<<endl;

            continue;

        }

        if (dep[t0] > dep[t1]) swap(t0, t1);

        pret1 = t1;

        pret0 = t0;

        int dist0 = 0,dist1 = 0;

        for (int i = MAX; i >= 0; i--)

            if (dep[t0] <= dep[t1] - pre[i]){

                t1 = p[t1][i];

                dist1 += pre[i];

            }

        //t1��t0����ͬһ�߶�

        if (t1 == t0)

        {

            if ((dist0+dist1)%2==0){

                int dis = (dist0+dist1)/2;

                int special = _get(pret1,dis);

                cout << _size[special] - _size[_get(pret1,dis-1)]<<endl;

            }else{

                cout<<0<<endl;

            }

            continue;

        }

        for (int i = MAX; i >= 0; i--)

        {

            if (p[t0][i] == p[t1][i]) continue;

            dist0+=pre[i];dist1+=pre[i];

            t0 = p[t0][i], t1 = p[t1][i];

        }

        dist0+=pre[0],dist1+=pre[0];

        t0 = p[t0][0];

        if (dist0==dist1){

            cout << _size[1]-_size[_get(pret0,dist0-1)]-_size[_get(pret1,dist1-1)] << endl;

        }else{

            if ((dist0+dist1)%2==0){

                int dis = (dist0+dist1)/2;

                int special = _get(pret1,dis);

                cout << _size[special] - _size[_get(pret1,dis-1)]<<endl;

            }else{

                cout<<0<<endl;

            }

        }

    }

    return 0;

}

巴特西

【Henu ACM Round#15 E】 A and B and Lecture Rooms

最新文章

热门文章