QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#438943#7677. Easy Diameter ProblemGraygooRE 274ms184636kbC++144.2kb2024-06-11 12:22:302024-06-11 12:22:30

Judging History

你现在查看的是最新测评结果

  • [2024-06-11 12:22:30]
  • 评测
  • 测评结果:RE
  • 用时:274ms
  • 内存:184636kb
  • [2024-06-11 12:22:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
const int mod = 1000000007;
vector<int> to[505];
int dd[305][2][305];
int tmp[305][305];
int ff[305];
int dep[305];
struct nd{
    int x,y,k,p;
    bool operator<(const nd&a)const{
        if(x!=a.x)return x<a.x;
        if(y!=a.y)return y<a.y;
        if(k!=a.k)return k<a.k;
        if(p!=a.p)return p<a.p;
    }
    bool operator==(const nd&a)const{
        return x==a.x and y==a.y and k==a.k and p==a.p;
    }
};
int n;
struct hashmap{
    int head[5000005];
    nd o[10000005];
    int vl[10000005];
    int nxt[10000005];
    int get(nd x){
        return (x.x*114514+x.y*1919810+x.k*998244353+x.p*10000007)%4999997;
    }
    int tot=0;
    int& operator[](const nd&a){
        int x=get(a);
        for(int i=head[x];i;i=nxt[i]){
            if(o[i]==a)return vl[i];
        }
        tot++;nxt[tot]=head[x];head[x]=tot;o[tot]=a;return vl[tot];
    }
    bool count(const nd&a){
        int x=get(a);
        for(int i=head[x];i;i=nxt[i]){
            if(o[i]==a)return 1;
        }
        return 0;
    }
}mp;
void dfs1(int x,int fa){
    ff[x]=fa;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs1(v,x);
    }
    return ;
}
void dfs2(int x,int fa){
    tmp[x][0]=1;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs2(v,x);
        for(int i=0;i<=n;i++)tmp[x][i+1]+=tmp[v][i];
    }
    return ;
}
int C[305][305];
int fac[305];
int solve(int x,int y,int k,int p){//x 这个子树或边 直径为y 除了k这个子树都有p的前置
    if(mp.count((nd){x,y,k,p}))return mp[(nd){x,y,k,p}];
    int ans=0;
    if(y==0)return mp[(nd){x,y,k,p}]=1;
    if(x>n){
        int a=x-n;
        int b=ff[a];
        int c=dd[a][0][(y-1)/2];
        int d=dd[a][1][(y-1)/2];
        if(k!=a){
            for(int i=0;i<c;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[c]%mod*solve(b,y-1,a,c-i))%mod;
            ans=(ans+fac[d]*solve(a,y-1,b,p+d))%mod;
        }else{
            ans=(ans+fac[c]*solve(b,y-1,a,p+c))%mod;
            for(int i=0;i<d;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[d]%mod*solve(a,y-1,b,d-i))%mod;
        }
    }else{
        auto calc=[&](int o){
            return o==ff[x]?dd[x][1][y/2-1]:dd[o][0][y/2-1];
        };
        int tot=0;
        for(auto v:to[x])tot+=calc(v);
        for(auto v:to[x]){
            int u=calc(v);
            if(!u)continue;
            int tar=v==ff[x]?x:v;tar+=n;
            int cur=tot-u;
            if(v==k){
                for(int i=0;i<cur;i++)ans=(ans+(i==0?1:C[i+p-1][i])*fac[cur]%mod*solve(tar,y-1,x,cur-i))%mod;
            }else{
                int oo=calc(k);
                int cc=cur-oo;
                int qq=solve(tar,y-1,x,cur+p);
                for(int i=0;i<=cc;i++){
                    if(cc-i+oo==0)continue;
                    ans=(ans+(i==0?1:C[i+p-1][i])*C[cc-i+oo][oo]%mod*fac[oo]%mod*fac[cc]%mod*qq)%mod;
                }
            }
        }
    }
    return mp[(nd){x,y,k,p}]=ans;
}
void dfs3(int x,int fa){
    dep[x]=dep[fa]+1;
    for(auto v:to[x]){
        if(v==fa)continue;
        dfs3(v,x);
    }
    return ;
}
signed main(){
  //  freopen("tree.in","r",stdin);
  //  freopen("tree.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    dfs1(1,0);
    for(int i=2;i<=n;i++){
        memset(tmp,0,sizeof(tmp));
        dfs2(i,ff[i]);
        for(int j=0;j<=n;j++)dd[i][0][j]=tmp[i][j];
        memset(tmp,0,sizeof(tmp));
        dfs2(ff[i],i);
        for(int j=0;j<=n;j++)dd[i][1][j]=tmp[ff[i]][j];
    }
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    dfs3(1,0);
    int x=max_element(dep+1,dep+n+1)-dep;
    dfs3(x,0);
    int y=max_element(dep+1,dep+n+1)-dep;
    dfs1(x,0);
    int t=y;
    for(int i=1;i<=dep[y]/2;i++)t=ff[t];
    int c=dep[y]%2==1?t:n+t;
    dfs1(1,0);
    cout<<solve(c,dep[y]-1,0,0)<<endl;
    assert(mp.tot<=5000000);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11840kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 12296kb

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 2ms
memory: 11992kb

input:

7
5 7
2 5
2 1
1 6
3 6
4 1

output:

116

result:

ok 1 number(s): "116"

Test #4:

score: 0
Accepted
time: 8ms
memory: 17124kb

input:

100
89 60
66 37
59 74
63 49
69 37
9 44
94 22
70 30
79 14
25 33
23 4
78 43
63 30
95 7
6 59
56 31
21 56
58 43
95 28
81 19
63 40
58 87
81 38
100 55
78 23
37 78
86 70
33 11
52 17
42 19
19 13
70 100
97 79
66 67
66 27
82 55
15 27
68 33
97 26
46 20
70 93
1 10
69 79
81 45
58 95
24 63
79 51
85 11
12 43
41 64...

output:

748786623

result:

ok 1 number(s): "748786623"

Test #5:

score: 0
Accepted
time: 34ms
memory: 30112kb

input:

300
109 123
221 101
229 22
114 101
110 258
50 79
26 1
238 47
140 271
77 213
140 125
19 179
111 96
194 114
57 101
1 251
19 13
92 238
114 116
193 140
153 238
1 173
252 220
1 22
124 197
196 214
196 224
1 138
201 90
184 56
266 154
71 184
46 15
256 27
1 69
1 32
22 182
237 196
111 1
279 91
139 196
114 80
...

output:

47013557

result:

ok 1 number(s): "47013557"

Test #6:

score: 0
Accepted
time: 25ms
memory: 24916kb

input:

300
1 77
259 130
51 79
130 1
104 58
196 26
48 112
106 22
285 30
263 252
79 196
247 134
1 41
15 133
285 100
105 72
40 217
48 62
61 183
217 261
48 86
284 12
10 106
270 230
211 285
103 27
234 16
105 288
263 68
106 194
36 130
283 88
263 217
285 21
24 27
79 75
133 153
285 157
65 293
37 133
1 56
226 152
1...

output:

160857944

result:

ok 1 number(s): "160857944"

Test #7:

score: 0
Accepted
time: 22ms
memory: 30756kb

input:

300
242 149
291 91
233 192
228 231
286 224
184 156
108 138
125 50
86 223
216 209
88 1
148 264
3 72
253 164
267 87
253 35
49 150
220 232
134 110
1 149
253 132
228 9
279 150
144 138
102 39
142 1
286 66
268 219
150 91
286 15
144 153
300 286
203 3
1 275
290 149
124 298
220 48
1 225
111 136
182 133
280 1...

output:

930240562

result:

ok 1 number(s): "930240562"

Test #8:

score: 0
Accepted
time: 18ms
memory: 29696kb

input:

300
1 236
187 186
155 44
272 1
40 47
204 39
285 197
26 243
285 59
185 77
42 209
69 220
76 55
179 173
175 238
209 18
204 277
69 147
250 44
239 1
109 15
72 185
69 131
285 127
194 112
1 285
199 299
90 35
113 42
180 256
196 209
126 292
187 56
202 286
165 204
109 1
204 20
40 209
216 201
112 79
187 176
20...

output:

881450286

result:

ok 1 number(s): "881450286"

Test #9:

score: 0
Accepted
time: 35ms
memory: 31260kb

input:

300
190 298
234 90
232 25
216 110
285 102
246 234
294 171
57 18
279 163
246 188
70 47
164 94
95 101
245 58
126 70
196 58
223 285
202 245
77 1
217 25
48 51
32 270
273 99
18 27
190 83
194 79
22 108
1 25
150 209
55 18
29 164
65 1
58 12
79 80
54 154
235 268
229 49
93 51
117 257
1 3
246 228
1 177
225 33
...

output:

41667252

result:

ok 1 number(s): "41667252"

Test #10:

score: 0
Accepted
time: 23ms
memory: 38356kb

input:

300
17 92
109 88
8 268
274 122
67 19
67 280
82 226
107 76
67 178
193 256
278 208
185 102
104 182
27 172
26 27
97 244
243 164
38 192
210 67
224 300
153 47
29 293
56 1
44 145
278 207
102 70
267 58
34 288
249 20
66 1
1 58
72 102
153 250
29 186
200 19
148 75
276 146
18 1
9 1
142 193
278 266
58 33
131 27...

output:

766720402

result:

ok 1 number(s): "766720402"

Test #11:

score: 0
Accepted
time: 33ms
memory: 31952kb

input:

300
91 264
183 296
84 43
37 244
187 89
85 243
66 230
64 57
71 172
32 283
176 190
176 269
255 18
159 283
66 232
9 202
66 222
60 172
172 290
107 208
89 290
137 239
218 47
81 29
161 110
109 171
221 67
14 236
25 155
48 298
39 254
176 280
180 66
192 113
276 155
56 273
290 43
29 289
194 124
234 266
68 35
...

output:

50070976

result:

ok 1 number(s): "50070976"

Test #12:

score: 0
Accepted
time: 27ms
memory: 35112kb

input:

300
15 7
281 65
183 284
99 55
151 93
93 29
213 183
197 155
157 76
174 226
33 143
167 36
11 176
72 262
157 237
123 262
225 151
1 151
207 225
225 265
205 281
157 251
226 117
224 290
20 218
264 278
220 69
242 195
191 253
267 99
138 11
275 115
132 242
226 270
91 248
292 226
125 11
76 38
33 159
43 281
36...

output:

832705434

result:

ok 1 number(s): "832705434"

Test #13:

score: 0
Accepted
time: 24ms
memory: 33000kb

input:

300
164 116
141 294
26 3
135 275
28 211
287 11
217 41
162 182
238 260
53 1
242 243
205 287
1 118
155 286
41 256
199 183
42 30
235 263
45 268
22 72
228 8
98 1
5 18
119 182
16 279
4 224
64 274
152 98
90 230
299 155
1 220
134 150
219 227
151 118
70 31
70 222
27 131
217 170
57 58
253 129
118 177
121 68
...

output:

101629452

result:

ok 1 number(s): "101629452"

Test #14:

score: 0
Accepted
time: 35ms
memory: 45276kb

input:

300
79 268
294 220
21 292
246 212
7 240
92 101
83 218
56 211
10 122
100 145
87 267
127 145
262 72
28 46
16 137
48 263
139 21
5 53
183 26
60 238
201 221
121 179
28 119
35 121
80 25
264 280
91 160
134 242
125 7
172 240
225 104
135 146
17 213
1 86
14 116
242 50
83 109
265 84
119 61
47 83
111 109
40 256...

output:

310258321

result:

ok 1 number(s): "310258321"

Test #15:

score: 0
Accepted
time: 36ms
memory: 46292kb

input:

300
192 25
131 179
181 92
56 148
237 182
117 243
67 191
124 276
109 246
74 105
78 266
240 29
20 40
223 230
8 19
179 162
273 272
212 72
27 208
235 26
226 48
273 267
136 277
210 132
231 242
172 177
18 231
33 67
22 133
189 167
239 41
68 165
67 38
280 101
233 230
88 203
61 117
54 226
274 74
118 290
185 ...

output:

453258233

result:

ok 1 number(s): "453258233"

Test #16:

score: 0
Accepted
time: 53ms
memory: 55784kb

input:

300
156 77
182 179
92 97
131 205
62 56
229 300
133 183
17 28
18 254
261 71
20 8
76 229
277 21
79 208
15 69
258 215
33 60
139 268
23 155
215 139
13 295
29 73
113 277
170 93
120 256
45 14
240 63
126 194
91 79
130 285
178 55
160 250
239 217
205 116
168 112
177 270
102 285
271 203
204 11
49 38
22 226
23...

output:

958129789

result:

ok 1 number(s): "958129789"

Test #17:

score: 0
Accepted
time: 42ms
memory: 59292kb

input:

300
119 249
283 2
56 179
44 78
151 230
192 268
97 190
113 211
63 98
208 268
280 103
138 69
129 292
201 224
272 298
164 35
122 184
252 132
195 182
109 94
209 165
35 201
247 267
107 112
210 86
112 235
72 211
257 10
141 274
217 297
272 290
286 219
8 59
118 170
276 214
127 193
203 41
256 115
27 96
185 7...

output:

140875750

result:

ok 1 number(s): "140875750"

Test #18:

score: 0
Accepted
time: 45ms
memory: 65240kb

input:

300
138 126
25 96
142 206
227 85
236 89
240 201
192 65
223 185
225 6
78 174
294 72
138 118
1 64
151 118
263 33
53 213
74 127
170 285
286 31
95 205
135 191
185 152
243 178
287 22
279 238
225 295
258 237
165 134
220 269
277 135
56 52
253 150
34 122
202 7
9 109
242 278
40 247
129 168
159 24
88 57
66 17...

output:

525372192

result:

ok 1 number(s): "525372192"

Test #19:

score: 0
Accepted
time: 58ms
memory: 65288kb

input:

300
282 97
194 58
153 187
281 262
160 224
179 25
127 123
68 63
75 156
260 163
177 101
158 255
238 56
267 96
132 122
123 265
282 29
162 58
73 59
166 116
185 9
157 191
141 81
297 255
228 216
269 177
190 175
10 114
125 244
66 79
241 30
33 176
182 44
36 128
207 241
65 124
39 38
227 68
90 291
152 268
17 ...

output:

866098103

result:

ok 1 number(s): "866098103"

Test #20:

score: 0
Accepted
time: 61ms
memory: 65804kb

input:

300
114 226
54 208
213 253
131 192
187 58
71 128
64 281
56 130
238 78
230 228
227 276
248 208
126 183
89 33
200 271
72 264
168 204
102 245
293 36
92 246
157 57
142 215
266 77
123 30
219 88
107 286
210 116
165 279
28 43
272 49
152 187
285 25
59 180
259 75
267 265
206 175
216 226
73 291
96 122
235 148...

output:

448016477

result:

ok 1 number(s): "448016477"

Test #21:

score: 0
Accepted
time: 61ms
memory: 70984kb

input:

300
200 109
91 267
131 106
186 52
216 131
277 227
80 239
86 149
222 90
220 112
219 16
48 150
69 249
82 138
42 1
209 5
195 235
291 146
56 261
141 70
12 66
244 37
55 122
33 241
174 172
295 78
288 151
254 270
298 132
60 146
97 281
12 246
144 28
8 292
121 163
242 197
261 10
278 100
120 211
278 35
28 290...

output:

997878224

result:

ok 1 number(s): "997878224"

Test #22:

score: 0
Accepted
time: 52ms
memory: 68856kb

input:

300
288 36
131 175
283 62
218 82
153 286
243 30
234 76
138 129
215 154
172 146
52 161
202 253
300 29
60 73
293 299
290 104
128 96
237 210
175 40
163 282
150 153
80 8
92 243
247 231
206 110
217 95
159 171
48 277
153 122
230 206
12 183
198 190
117 47
77 211
195 258
23 248
136 211
155 209
72 116
55 202...

output:

120554047

result:

ok 1 number(s): "120554047"

Test #23:

score: 0
Accepted
time: 59ms
memory: 66704kb

input:

300
47 46
292 281
41 8
211 141
62 272
109 265
12 217
156 294
272 298
90 73
131 244
69 149
138 45
90 46
77 67
43 246
55 108
128 148
27 20
30 210
88 121
109 143
289 42
35 4
264 131
38 111
134 239
164 241
101 141
256 68
179 135
262 127
79 31
266 251
30 157
282 77
198 115
112 10
27 250
2 298
183 184
8 2...

output:

684841907

result:

ok 1 number(s): "684841907"

Test #24:

score: 0
Accepted
time: 59ms
memory: 70288kb

input:

300
112 92
68 170
52 166
147 13
283 150
151 13
128 18
158 250
3 6
140 118
300 207
171 168
77 135
38 247
291 125
222 253
138 204
70 152
3 153
91 24
89 87
165 77
41 69
184 36
163 242
137 218
101 78
87 259
226 290
272 156
85 45
107 179
148 11
148 166
212 1
105 26
285 198
173 286
104 144
75 36
130 221
2...

output:

505448774

result:

ok 1 number(s): "505448774"

Test #25:

score: 0
Accepted
time: 67ms
memory: 70828kb

input:

300
223 291
260 121
235 126
290 285
184 99
266 294
20 85
65 208
18 125
127 146
80 118
82 169
248 66
35 160
295 171
103 91
235 238
289 29
239 81
225 23
255 140
84 71
38 224
202 181
54 72
53 300
272 258
261 139
196 15
58 46
297 204
291 237
86 43
228 206
98 185
187 123
12 65
16 97
203 113
25 104
1 184
...

output:

727627477

result:

ok 1 number(s): "727627477"

Test #26:

score: 0
Accepted
time: 28ms
memory: 34148kb

input:

300
159 130
18 130
7 159
84 159
26 18
13 18
140 7
143 7
265 84
181 84
123 26
241 26
94 13
76 13
281 140
2 140
14 143
1 143
260 265
72 265
4 181
96 181
51 123
121 123
193 241
191 241
197 94
20 94
226 76
208 76
161 281
27 281
199 2
217 2
45 14
63 14
223 1
240 1
196 260
32 260
236 72
5 72
214 4
255 4
1...

output:

314246397

result:

ok 1 number(s): "314246397"

Test #27:

score: 0
Accepted
time: 274ms
memory: 184636kb

input:

300
32 172
32 33
32 187
32 193
32 194
32 294
32 86
32 24
32 218
32 266
32 147
32 199
32 137
32 114
32 123
32 126
32 188
32 168
32 281
32 175
32 221
32 48
32 288
32 254
32 212
32 81
32 278
32 75
32 64
32 141
32 245
32 215
32 255
32 185
32 277
32 92
32 236
32 182
32 161
32 227
32 54
32 35
32 184
32 79...

output:

78513551

result:

ok 1 number(s): "78513551"

Test #28:

score: 0
Accepted
time: 115ms
memory: 104248kb

input:

300
228 245
228 207
228 125
228 241
228 300
228 80
228 213
228 175
228 119
228 78
228 53
228 129
228 83
228 204
228 212
228 217
228 214
228 225
228 188
228 206
228 132
228 221
228 244
228 167
228 103
228 169
228 73
228 190
228 177
228 231
228 23
228 147
228 286
228 63
228 293
228 261
228 243
228 267...

output:

32972061

result:

ok 1 number(s): "32972061"

Test #29:

score: 0
Accepted
time: 80ms
memory: 84416kb

input:

300
280 296
280 141
280 114
280 179
280 292
280 39
280 96
280 17
280 160
280 89
280 192
280 126
280 119
280 217
280 109
280 208
280 205
280 135
280 249
280 255
280 261
280 4
280 220
280 289
280 270
280 138
280 184
217 207
280 66
280 72
280 165
109 288
280 252
280 23
280 284
280 260
280 212
280 53
28...

output:

622080990

result:

ok 1 number(s): "622080990"

Test #30:

score: 0
Accepted
time: 47ms
memory: 69752kb

input:

300
66 279
66 156
66 72
66 225
66 231
66 47
72 148
66 89
225 222
66 135
66 240
66 81
66 19
66 157
66 107
66 262
66 76
240 20
66 133
156 69
66 118
66 82
156 121
66 189
66 211
66 206
66 233
66 38
66 166
66 163
189 86
66 187
66 144
66 173
66 197
66 212
66 271
66 247
66 87
66 248
66 73
240 6
66 37
66 59...

output:

610429360

result:

ok 1 number(s): "610429360"

Test #31:

score: 0
Accepted
time: 47ms
memory: 63320kb

input:

300
54 88
54 138
54 126
54 14
54 21
54 50
54 81
88 69
14 59
54 128
126 198
54 70
54 208
54 71
54 260
54 109
54 199
109 4
54 121
54 145
54 264
54 214
54 209
81 226
54 190
54 212
54 62
54 113
54 245
54 118
145 135
260 7
54 247
54 165
54 3
54 235
165 219
54 246
54 146
54 170
54 272
54 297
54 8
54 230
5...

output:

118463559

result:

ok 1 number(s): "118463559"

Test #32:

score: 0
Accepted
time: 2ms
memory: 11760kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #33:

score: 0
Accepted
time: 2ms
memory: 11784kb

input:

2
2 1

output:

2

result:

ok 1 number(s): "2"

Test #34:

score: 0
Accepted
time: 16ms
memory: 18036kb

input:

300
96 1
1 91
1 279
1 90
30 1
210 1
1 220
140 1
1 229
52 1
66 1
1 287
1 276
92 1
1 225
1 249
1 70
71 1
1 31
193 1
144 1
289 1
1 223
180 1
103 1
201 1
1 10
1 149
145 1
1 224
11 1
1 95
221 1
118 1
1 113
1 251
134 1
203 1
54 1
1 192
1 215
1 267
24 1
1 37
39 1
1 35
9 1
1 115
1 236
1 241
1 242
1 280
1 13...

output:

56129785

result:

ok 1 number(s): "56129785"

Test #35:

score: -100
Runtime Error

input:

300
67 70
101 222
228 281
165 260
208 197
224 7
176 211
220 177
196 38
282 145
113 13
231 56
254 300
273 50
67 10
291 226
95 169
159 112
19 169
51 3
281 252
103 34
91 81
156 26
181 83
48 158
270 201
199 79
152 217
223 179
187 32
290 224
220 134
190 34
216 266
122 294
154 44
4 175
268 244
78 23
140 1...

output:

661025383

result: