Zakiro


私信TA

用户名:dotcpp0756568

访问量:68

签 名:

等  级
排  名 57730
经  验 208
参赛次数 0
文章发表 2
年  龄 0
在职情况 学生
学  校 常熟理工学院
专  业

  自我简介:

TA的其他文章

机房,LCA+dp
浏览:29

解题思路:先求lca,在建树的过程中dp成型,最后算,我用的重链剖分求LCA

注意事项:

参考代码:

#include<bits/stdc++.h>

#define int long long

#define endl '\n'

using namespace std;


const int N=1e6+10;

vector<int> v[N];

int n,m,s;


int sz[N];//子树大小

int fa[N];//父亲节点

int dep[N];//节点深度

int son[N];//重儿子

int top[N];//点所在重链的顶点

int dp[N];


void dfs1(int u,int sum)

{

    sz[u] = 1;  // 初始化当前节点 u 的子树大小为 1(自身)

    dep[u] = dep[fa[u]] + 1;  // 计算当前节点 u 的深度,等于其父节点的深度加 1

    int l=v[u].size();

    dp[u]=l+sum;

    for (auto x : v[u])  // 遍历节点 u 的所有邻接节点(子节点)

    {

        if (x == fa[u])  // 如果 x 是 u 的父节点,则跳过

            continue;

        fa[x] = u;  // 设置 x 的父节点为 u

        dfs1(x,dp[u]);  // 递归处理子节点 x

        sz[u] += sz[x];  // 累加子节点 x 的子树大小到当前节点 u


        // 如果当前子节点 x 的子树大小大于当前记录的重儿子的子树大小

        if (sz[x] > sz[son[u]])

            son[u] = x;  // 更新重儿子为 x

    }

}



void dfs2(int u, int h)

{

    top[u] = h;  // 将当前节点 u 所在的重链的顶端节点设置为 h

    if (son[u])  // 如果 u 有重儿子

        dfs2(son[u], h);  // 对重儿子进行 dfs,并且顶端节点仍然是 h


    for (auto x : v[u])  // 遍历 u 的所有子节点

    {

        if (x == fa[u] || x == son[u])  // 跳过父节点和重儿子

            continue;

        dfs2(x, x);  // 对于轻儿子,重新开启一条新的重链,顶端节点设置为自己

    }

}



int lca(int x, int y)

{

    while (top[x] != top[y])  // 当 x 和 y 不在同一条重链上时

    {

        if (dep[top[x]] > dep[top[y]])  // 比较两者所在重链顶端节点的深度

            x = fa[top[x]];  // x 跳到其所在重链顶端节点的父节点

        else

            y = fa[top[y]];  // y 跳到其所在重链顶端节点的父节点

    }

    // 当 x 和 y 在同一条重链上时,返回深度较小的那个节点

    return dep[x] < dep[y] ? x : y;

}




void slove()

{

    cin>>n>>m;

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

    {

        int x,y;

        cin>>x>>y;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    dfs1(1,0);

    dfs2(1,1);

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

    {

        int x,y;

        cin>>x>>y;

        int d=lca(x,y);

        cout<<dp[x]+dp[y]-dp[d]-dp[fa[d]]<<endl;

    }

}


signed main()

{

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

    int _=1;

    //cin>>_;

    while(_--)

    {

        slove();

    }

    return 0;

}


 

0.0分

0 人评分

  评论区