QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283839#7677. Easy Diameter ProblemMax_s_xaMTL 280ms203604kbC++146.3kb2023-12-15 16:22:432023-12-15 16:22:44

Judging History

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

  • [2023-12-15 16:22:44]
  • 评测
  • 测评结果:TL
  • 用时:280ms
  • 内存:203604kb
  • [2023-12-15 16:22:43]
  • 提交

answer

#include <iostream>
#include <vector>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 310, MAXM = 610, mod = 1e9 + 7;

int n;
vector <int> e[MAXN];

ll fac[MAXM], inv[MAXM];
inline ll C(int n, int m) {return (n < m || m < 0 ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod);}
inline ll Calc(int n, int m) {return (n == 0 || m < 0 ? 1 : C(n + m, m));}

int ev[MAXN][2], eid[MAXN][MAXN];
int dis[2][MAXN][MAXN], cnt[2][MAXN][MAXN];
int len, Mid, Midt;
void DFS(int u, int fa, int rt, bool d)
{
    cnt[d][rt][dis[d][rt][u]]++;
    for (auto v : e[u])
        if (v != fa)
        {
            dis[d][rt][v] = dis[d][rt][u] + 1;
            DFS(v, u, rt, d);
        }
}
inline void Init()
{
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for (int i = 2; i < MAXM; i++) fac[i] = fac[i - 1] * i % mod, inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 2; i < MAXM; i++) inv[i] = inv[i - 1] * inv[i] % mod;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 2; j++)
            DFS(ev[i][j], ev[i][j ^ 1], i, j);
        int cur = 1;
        for (int j = n; j >= 0; j--)
            if (cnt[0][i][j]) {cur += j; break;}
        for (int j = n; j >= 0; j--)
            if (cnt[1][i][j]) {cur += j; break;}
        if (len < cur || (len == cur && !Mid))
        {
            len = cur;
            if (cnt[0][i][(len - 1) / 2] && cnt[1][i][len / 2])
                Mid = i, Midt = 1;
            else if (cnt[1][i][(len - 1) / 2] && cnt[0][i][len / 2])
                Mid = i, Midt = 0;
        }
    }
}

int f[MAXN][2][MAXN << 1][MAXN];

int main()
{
    // freopen("cpr.in", "r", stdin);
    // freopen("cpr.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n);
    for (int i = 1, u, v; i < n; i++)
    {
        Read(u), Read(v);
        ev[i][0] = u, ev[i][1] = v;
        eid[u][v] = eid[v][u] = i;
        e[u].push_back(v), e[v].push_back(u);
    }
    Init();
    // cout << len << " " << Mid << "\n";
    // for (int i = 1; i < n; i++)
    // {
    //     for (int j = 1; j <= n; j++) cout << dis[0][i][j] << ' ';
    //     cout << "\n";
    //     for (int j = 1; j <= n; j++) cout << dis[1][i][j] << " ";
    //     cout << "\n\n";
    // }
        
    for (int i = 1; i < n; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < n - 1; k++)
                f[i][j][1][k] = 2;
    for (int r = 2; r <= len; r++)
    {
        for (int i = 1; i < n; i++)
            for (int j = 0; j < 2; j++)
            {
                if (r == len && i != Mid) continue;
                int u = ev[i][j], w = ev[i][j ^ 1], Eid, Vid;
                int cntw, cntu;
                for (int k = 0; k < n - r; k++)
                {
                    // cout << i << " " << j << " " << r << " " << k << " #:\n";
                    if (r & 1)
                    {
                        cntw = cnt[j ^ 1][i][r - 1 >> 1];
                        f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j][r - 1][k + cntw] * fac[cntw]) % mod;
                    }
                    else
                    {
                        cntw = cnt[j ^ 1][i][r - 2 >> 1];
                        for (auto v : e[u]) if (v != w)
                        {
                            Eid = eid[v][u], Vid = (ev[Eid][1] == v);
                            cntu = cnt[j][i][r >> 1] - cnt[Vid][Eid][r - 2 >> 1];
                            // cout << Eid << " " << Vid << " " << r - 1 << " " << k << " " << cntu << " " << cntw << "\n";
                            f[i][j][r][k] = (f[i][j][r][k] + (ll)f[Eid][Vid][r - 1][k + cntu + cntw] * fac[cntw] % mod * fac[cntu] % mod * Calc(cntu, k + cntw)) % mod;
                            // cout << f[i][j][r][k] << "\n";
                        }
                    }
                    cntu = cnt[j][i][r >> 1];
                    if (!k) f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][cntu] * fac[cntu]) % mod;
                    else for (int m = 1; m <= cntu; m++)
                        f[i][j][r][k] = (f[i][j][r][k] + (ll)f[i][j ^ 1][r - 1][m] * fac[cntu] % mod * Calc(cntu - m, k - 1)) % mod;
                }
            }
    }
    // for (int r = 1; r <= len; r++, cout << "\n")
    //     for (int i = 1; i < n; i++, cout << "\n")
    //         for (int j = 0; j < 2; j++)
    //             for (int k = 0; k < n; k++) cout << f[i][j][r][k] << " ";
    ll ans = 0;
    if (len & 1) ans = f[Mid][0][len][0];
    else ans = f[Mid][Midt][len][0];
    cout << ans << "\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7732kb

input:

3
1 2
3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

5
4 1
4 5
1 2
1 3

output:

28

result:

ok 1 number(s): "28"

Test #3:

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

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: 7ms
memory: 98996kb

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: 207ms
memory: 103096kb

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: 104ms
memory: 86480kb

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: 177ms
memory: 97636kb

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: 157ms
memory: 126184kb

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: 198ms
memory: 134128kb

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: 232ms
memory: 139468kb

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: 242ms
memory: 144372kb

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: 192ms
memory: 176632kb

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: 224ms
memory: 162540kb

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: 224ms
memory: 167228kb

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: 238ms
memory: 179804kb

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: 211ms
memory: 194144kb

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: 214ms
memory: 190772kb

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: 280ms
memory: 197180kb

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: 222ms
memory: 199664kb

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: 229ms
memory: 196828kb

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: 261ms
memory: 200812kb

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: 219ms
memory: 195840kb

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: 260ms
memory: 200592kb

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: 278ms
memory: 203604kb

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: 280ms
memory: 201120kb

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: 76ms
memory: 190152kb

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: -100
Time Limit Exceeded

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:


result: