luogu P5002 專心OI - 找祖先

題目描述

Imakf是一個小蒟蒻，他最近剛學了LCA，他在手機APP裡看到一個遊戲也叫做LCA就下載下傳了下來。

這個遊戲會給出你一棵樹，這棵樹有N個節點，根結點是R，系統會選中M個點P1,P2...PM，要Imakf回答有多少組點對(ui,vi)的最近公共祖先是Pi。Imakf是個小蒟蒻，他就算學了LCA也做不出，于是隻好求助您了。

Imakf畢竟學過一點OI,是以他允許您把答案模 (10^9+7)

輸入格式

第一行 N , R , M

此後N-1行 每行兩個數a,b 表示a,b之間有一條邊

此後1行M個數 表示P_i

輸出格式

M行，每行一個數，第i行的數表示有多少組點對(u_i,v_i)的最近公共祖先是P_i

N≤10000,M≤50000

顯然這題根LCA沒有多大關系......

設size(x)表示以x為根的子樹大小(x自己也要算)，我們來愉快地推式子

設存在點u,v，并且x是u,v的祖先。考慮u,v之間的路徑(不包含u,v)不經過x，那麼根據往日做LCA的經驗，隻有當u,v至少其中一個等于x時兩個點的LCA才會是x。設x一共有k棵子樹，那麼此時：

\[ ans1=\sum_{i=1}^{k}size[son[i]]*2+1=size[x]*2-1 \]

再考慮經過x的情況，此時：

\[ ans2=\sum_{i=1}^{k}\sum_{j=1}^{k}size[son[i]]*size[son[j]] \]

\[ ans2=\sum_{i=1}^{k}size[son[i]]*(size[x]-1) \]

\[ ans2=(size[x]-1)^2 \]

然後減去重複計算的i=j的部分:

\[ ans2=(size[x]-1)^2-\sum_{i=1}^{k}size[i]^2 \]

再把兩個答案加起來:

\[ ans=ans1+ans2=size[x]*2-1+(size[x]-1)^2-\sum_{i=1}^{k}size[i]^1 \]

\[ ans=size[x]^2-\sum_{i=1}^{k}size[i]^2 \]

然後我們來分析複雜度。最壞的情況就是：根直接連接配接其餘所有點，并且每次詢問都是根節點。此時時間複雜度就是O(N*M)。考慮優化。

顯然重複計算過的我們不需要再算。記錄ans數組，預處理出每個點的答案，時間複雜度就變成了O(N+M)，期望得分100。

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 10001
#define p 1000000007
using namespace std;

struct edge{
    int to,next;
    edge(){}
    edge(const int &_to,const int &_next){ to=_to,next=_next; }
}e[maxn<<1];
int head[maxn],k;

int size[maxn],ans[maxn];
int n,m,r;

inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
inline void add(const int &u,const int &v){
    e[k]=edge(v,head[u]);
    head[u]=k++;
}

inline void dfs(int u,int pre){
    size[u]=1;
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==pre) continue;
        dfs(v,u),size[u]+=size[v];
        ans[u]=(ans[u]+size[v]*size[v])%p;
    }
    ans[u]=(size[u]*size[u]%p-ans[u]+p)%p;
}

int main(){
    memset(head,-1,sizeof head);
    n=read(),r=read(),m=read();
    for(register int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs(r,0);

    while(m--) printf("%d\n",ans[read()]);
    return 0;
}                

*相減的部分取餘需要判負數......或者直接加個p上去

轉載于:https://www.cnblogs.com/akura/p/10837547.html