洛谷P5002 专心OI - 找祖先

题目背景
Imakf是一个小蒟蒻,他最近刚学了LCA,他在手机APP里看到一个游戏也叫做LCA就下载了下来。

题目描述
这个游戏会给出你一棵树,这棵树有NN个节点,根结点是RR,系统会选中MM个点P_1,P_2…P_M ,要Imakf回答有多少组点对(u_i,v_i)的最近公共祖先是P_i 。Imakf是个小蒟蒻,他就算学了LCA也做不出,于是只好求助您了。Imakf毕竟学过一点OI,所以他允许您把答案模 (10^9+7)(
9 +7)

输入格式
第一行 N , R , M
此后N-1行 每行两个数a,ba,b 表示a,ba,b之间有一条边
此后1行 M个数 表示P_i
输出格式
M行,每行一个数,第ii行的数表示有多少组点对(u_i,v_i)的最近公共祖先是P_i

题解: 本来想写点求lca的题,看见这个标签有Lca就进来了

然而这题和求lca一点关系没有

简单地分析了一下题目,两个两个求lca再判断方法必然会tle,于是我们考虑一些其他的做法。废话

首先,两个点的lca如果是p的话,我们不难发现,如果有一个点不是p,那么这两个点必然位于p的两个不同子树中,否则就会有一个深度更深的爸爸取代他。

于是我们可以考虑,对于p的每一个子树,必有(size[p]-size[son])*size[son]个合法解,这个式子代表的是p的这棵子树中的每一个点和其他子树中的每一个点构成一对,因为不在一棵子树中,所以p必然是他们两个的lca。把这些加起来之后,p的子树中的任何一个点和p都可以构成一对,而由样例可以知道,p和p自己也是一对,所以再在上面的式子基础上加上size[p]。此题就结束了。 因为(u,v)(v,u)算两组解,所以这样必然是对的,上代码 (m比n大,所以可以先全算出来啦)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define fo(i) for(int i=1;i<n;i++)
#define Fo(j) for(int j=1;j<=m;j++)
using namespace std;
const int N=500005;
const int M=2000003;
const int modd=1e9+7;
int n,m,s,tot;
int head[N];
int dep[N],ans[N];
struct NODE{
   
	int to,nex;
}bian[M];
struct Node{
   
    int son,dep,fa;
}dian[N];
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y){
   
	++tot;
	bian[tot].nex=head[x];
	bian[tot].to=y;
	head[x]=tot;
}
void dfs(int xx,int fa){
   
    dian[xx].son=1;
    for(int i=head[xx];i;i=bian[i].nex){
   
        if(bian[i].to!=fa){
   //这个儿子不是爹
             dian[bian[i].to].fa=xx;
             dian[bian[i].to].dep=dian[xx].dep+1;
             dfs(bian[i].to,xx);
             dian[xx].son+=(dian[bian[i].to].son%modd);
        }
    }
}
inline int solve(int xx){
   
     int ans=dian[xx].son;
     for(int i=head[xx];i;i=bian[i].nex){
   	
          if(dian[bian[i].to].dep>dian[xx].dep){
           	   
               ans=ans+(dian[xx].son-dian[bian[i].to].son)*dian[bian[i].to].son;
          }
     }
     return ans;
     
}
int main(){
   
    n=read();s=read();m=read();
    fo(i){
   
       int a,b;
       a=read();b=read();
       add(a,b); add(b,a);
    }
    dian[0].dep=0;
    dfs(s,0);
    for(int i=1;i<=n;i++) ans[i]=solve(i);
    Fo(j){
   
        int p;
        p=read();
        printf("%d\n",ans[p]);
    }
	return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议