洛谷 5002 专心 OI - 找祖先

这题貌似很 naive 呢……
根本不需要取模的说，n 个数中数对的个数最多是 n2=108。 首先，询问 p，LCA 为 p 的点对有两种情况： - 至少一个为 p。 - 分别在两棵以 p 的不同儿子构成的子树中。

前一种很好理解，后一种若它们在同一棵子树中，很显然可以找到 p 的一个儿子为更近的祖先。
并且注意点对是区分顺序的。

设 sizep 表示以 p 为根的子树的结点个数，sonp 表示 p 的儿子的集合，
第一种情况就是 2sizep−1，因为 (p,p) 重复所以要 − 1。
第二种情况，∑∀x,y∈sonp,x≠ysizex⋅sizey，但是这样还不够优，所以可以优化为 ∑∀x∈sonpsizex⋅(sizep−sizex−1)。

此外数据范围显示有可能 m>n，所以我们可以记忆化一下，以免被菊花图询问 m 次根的毒瘤数据卡掉。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e4;
const int mod = 1e9 + 7;
int n,r,m;
int to[(N << 1) + 10],pre[(N << 1) + 10],first[N + 10],ans[N + 10];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
int q[N + 10],head,tail,sz[N + 10],fa[N + 10];
int main()
{
    memset(ans,-1,sizeof ans);
    scanf("%d%d%d",&n,&r,&m);
    int u,v;
    for(register int i = 1;i < n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    q[++tail] = r;
    int p;
    while(head < tail)
    {
        p = q[++head];
        sz[p] = 1;
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
            {
                fa[to[i]] = p;
                q[++tail] = to[i];
            }
    }
    for(register int i = n;i;--i)
        sz[fa[q[i]]] += sz[q[i]];
    while(m--)
    {
        scanf("%d",&p);
        if(ans[p] ^ -1)
            printf("%d\n",ans[p]);
        else
        {
            ans[p] = ((sz[p] << 1) - 1) % mod;
            for(register int i = first[p];i;i = pre[i])
                if(to[i] ^ fa[p])
                    ans[p] = (ans[p] + sz[to[i]] * (sz[p] - sz[to[i]] - 1)) % mod;
            printf("%d\n",ans[p]);
        }
    }
}