不平凡的许愿树

【题目描述】

noip要到了，大家来到许愿树前。这个许愿树不仅仅是许愿树，还有未卜先知的功能。众OIer问许愿树：“不平凡的许愿树，CCF告诉我们noip中会有两道题目从Openjudge上选择，你能不能告诉我是哪两道题。”

许愿树想了想直接说出答案并不妥：“中国有句古话叫‘闷声大发财’，我就什么也不说，这是最好的。但是我看到你们这么热情，一句话不说也不好，我就告诉你们点信息吧。你们看我是一个由N个结点组成的树，在树中任选着3个点，有多少种选择方案使得这三个点互相之间的距离相同？两个方案不同当且仅当一个点在第一种方案中被选择，第二种方案中没有被选择。”

“记你算出来方案数为cnt，那么第一道题的题号就是cnt%338 + 1，第二题的题目编号是(cnt+233)%338+1。”

可是OIer们手头并没有计算机，于是请你来告诉他们题目编号。

【输入格式】

第一行一个整数N，表示树有N个点。

接下来N-1行，每行两个整数u,v，表示树中有一条从u到v的边

【输出格式】

一行，两个整数，分别为预测的第一题题号和第二题题号。

【样例输入】

【样例输出】

6 239

【提示】

样例解释：

共有5种方案，分别是{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}。所以第一题的编号为5%338 + 1 = 6；第二题的编号为(5+233)%338 + 1 = 239;

数据范围与约定：

对于30%的数据：1 <= n <= 100

对于60%的数据：1 <= n <= 1500

对于100%的数据：1 <= n <= 5000

题解：

显然不知道怎么dp 就乱搞，又显然以每个点dfs然后组合O（n^2）但看到样例就知道重复统计了

所以我强制规定三元点对必须分布在三颗不同子树上，就不会重复了...............................................

然后就来了个(n*log3n)≈(n^2)的玄学方法结果跑得还挺快

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 const int N=5005,mod=338;
 8 int n,head[N],num=0,du[N];
 9 struct Lin{
10     int next,to;
11 }a[N<<1];
12 void init(int x,int y){
13     a[++num].next=head[x];
14     a[num].to=y;
15     head[x]=num;
16 }
17 int t[N],c[N][N],sz[N];
18 void dfs(int x,int last,int dep,int rt){
19     int u;
20     t[dep]++;
21     for(int i=head[x];i;i=a[i].next){
22         u=a[i].to;
23         if(u==last || u==rt)continue;
24         dfs(u,x,dep+1,rt);
25     }
26 }
27 int ans=0,sum[N];
28 void solve(){
29     for(int i=1;i<=n;i++){
30         if(!sz[i])break;
31         for(int j=1;j<=sz[i];j++)sum[j]=sum[j-1]+c[i][j];
32         for(int j=1;j<sz[i]-1;j++){
33             for(int k=j+1;k<sz[i];k++){
34                 ans+=(sum[sz[i]]-sum[k])*c[i][j]*c[i][k];
35                 ans%=mod;
36             }
37         }
38         sz[i]=0;
39     }
40 }
41 int main()
42 {
43     freopen("hopetree.in","r",stdin);
44     freopen("hopetree.out","w",stdout);
45     scanf("%d",&n);
46     int x,y;
47     for(int i=1;i<n;i++){
48         scanf("%d%d",&x,&y);
49         init(x,y);init(y,x);
50         du[x]++;du[y]++;
51     }
52     for(int i=1;i<=n;i++)
53     {
54         if(du[i]<3)continue;
55         for(int j=head[i];j;j=a[j].next){
56             dfs(a[j].to,a[j].to,1,i);
57             for(int k=1;k<=n;k++){
58                 if(!t[k])break;
59                 c[k][++sz[k]]=t[k];
60                 t[k]=0;
61             }
62         }
63         solve();
64     }
65     printf("%d %d
",ans+1,((ans+233)%mod)+1);
66 }