题目概述

给你 $n$ 个点，每个点有一个 $[1,n]$ 的随机权值，问有多少回文路径。

解题报告

因为是随机的……所以你要有信仰，假装回文路径长度最多只有 $5$ 就行了。

然后因为他只有 $3s$ 时限……你会TLE不止（小常数巨佬们当我没说）……

我们再来理性分析一波：一个串是回文串的概率为 $({1\over n})^{len/2}$ ，当 $len=4$ 的时候概率就只有 $10^{-10}$ 了真棒 。

所以我们只要考虑 $len\le 3$ 的情况就行了，瞎搞搞。

ps：$n$ 非常小的时候最好还是 $O(n^2)$ 处理，但是BZOJ没卡我，不想管了XD……

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,HASH=19260817;

int te,n,a[maxn+5],tp;long long ans;
int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E
int sum[HASH],stk[maxn+5];
inline void Insert(int x) {if (sum[x]) sum[x]++; else stk[++stk[0]]=x,sum[x]=1;}
inline void Clear() {while (stk[0]) sum[stk[stk[0]--]]=0;}
int main(){
    freopen("H.in","r",stdin);
    freopen("H.out","w",stdout);
    for (readi(te);te;te--){
        readi(n);for (int i=1;i<=n;i++) readi(a[i]);
        E=0;memset(lnk,0,sizeof(lnk));ans=n;
        for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
        for (int i=1;i<=n;i++,Clear())
            for (int j=lnk[i];j;j=nxt[j])
                ans+=sum[a[son[j]]],Insert(a[son[j]]);
        for (int i=1;i<=n;i++)
            for (int j=lnk[i];j;j=nxt[j],Clear())
                if (a[i]==a[son[j]]&&i>son[j]){
                    ans++;
                    for (int t=lnk[i];t;t=nxt[t])
                        if (son[t]!=son[j]) Insert(a[son[t]]);
                    for (int t=lnk[son[j]];t;t=nxt[t])
                        if (son[t]!=i) ans+=sum[a[son[t]]];
                }
        printf("%lld\n",ans);
    }
    return 0;
}