解題區/解題區 - UVa

UVa 12785 - Emacs Plugin

Problem

每個 * 位置，可以任意替換成任何字串或者是空字串，是問是否有可能匹配主字串。

Sample Input

1
2
3
4
5
6
7
8
9
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x

Sample Output

1
2
3
4
5
yes
no
yes
yes
no

Solution

以 * 劃分，將其切割成好幾個 token，根據貪心原則只要按照順序出現這些 token 即可，因此盡可能靠左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <sstream>
using namespace std;
#define MAXN 100005
char P[MAXN], T[MAXN];
int kmpTable[MAXN];
void KMPtable(const char *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(const char *T, int tlen, const char *P, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1)
        	return i;
    }
    return -1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, plen, tlen;
    string token;
    while (scanf("%d", &n) == 1) {
        while (getchar() != '\n');
        gets(P);
        plen = strlen(P);
        for (int i = 0; i < n; i++) {
            gets(T);
            for (int j = 0; T[j]; j++) {
                if (T[j] == '*')
                    T[j] = ' ';
            }
            stringstream sin(T);
            int start = 0;
            while (sin >> token) {		
                KMPtable(token.c_str(), token.length());
                int test = KMPmatching(P + start, plen - start, token.c_str(), token.length());
//				printf("%s %d %s\n", token.c_str(), test, P + start);
                if (test == -1)	 {start = -1; break;}
                start += test + 1;
            }
            puts(start == -1 ? "no" : "yes");
        }
    }
    return 0;
}
/*
4
heyhelloyou
hel*
*o*e
e*o
hello
1
hello
x
10
rwoeyhtdvtswftfguuujqxdxdqylkyqaahianzbejckxbgeybq
oexktdvtswftf*w*n*q*rvdloll*qr
kdd*ts*ftv**ur**cdx*qi
*dtlk
**q**g****a**n
*/
Read More +
解題區/解題區 - UVa

UVa 10597 - Right Words

Problem

對一個已經是 Chomsky normal form 的 CFG，問一個 string 是否在 CFG 之中。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
S
SABC
ab
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
# -> #
baaba
ab
abaa
a
aaaaa
bbbbb
#
S
SAB
ab
S -> AB
A -> AA
A -> a
B -> b
# -> #
ab
aaab
aba
baaaaaaaa
abbbbbb
aaaaaba
baaaaaaaab
aaaa
a
ab
#

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
baaba is in L(G)
ab is in L(G)
abaa is in L(G)
a is not in L(G)
aaaaa is in L(G)
bbbbb is not in L(G)
 
ab is in L(G)
aaab is in L(G)
aba is not in L(G)
baaaaaaaa is not in L(G)
abbbbbb is not in L(G)
aaaaaba is not in L(G)
baaaaaaaab is not in L(G)
aaaa is not in L(G)
a is not in L(G)
ab is in L(G)

Solution

因為 chomsky normal form 恰好劃分成兩個，定義字串 dp[l][r] 中可以解析出那些 nonterminal，藉由矩陣鍊乘積的方式，將其組合。最後檢查整個字串是否可以推回 start symbol。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <string.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    char s1[1024], s2[1024];
    while (scanf("%s", s1) == 1) {
        char start = s1[0];
        scanf("%*s %*s");
        set<char> re[128];
        set<char> rule[128][128];
        while (scanf("%s -> %s", s1, s2) == 2 && s1[0] != '#') {
            if (s2[1] == '\0')
                re[s2[0]].insert(s1[0]);
            else {
                rule[s2[0]][s2[1]].insert(s1[0]);
            }
        }
        while (scanf("%s", s1) == 1 && s1[0] != '#') {
            int n = strlen(s1);
            set<char> dp[64][64];
            for (int i = 0; i < n; i++) {
                dp[i][i].insert(re[s1[i]].begin(), re[s1[i]].end());
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; i + j < n; j++) {
                    for (int k = j; k < i+j; k++) {
                        for (set<char>::iterator a = dp[j][k].begin();
                            a != dp[j][k].end(); a++)
                        for (set<char>::iterator b = dp[k+1][i+j].begin();
                            b != dp[k+1][i+j].end(); b++)
                            dp[j][i+j].insert(rule[*a][*b].begin(), rule[*a][*b].end());
                    }
                }
            }
            printf("%s is %sin L(G)\n", s1, dp[0][n-1].find(start) == dp[0][n-1].end() 
                                        ? "not " : "");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/出題解題

[ACM 題目] 災難再臨

Description

Background

還記得那些年我們已經經歷的災難嗎？PTC201410D！ZJOI 2012 DAY2！如果不記得，接著請聽我捏造個故事。

Problem

危險種這一類的怪物，不斷地在村莊肆虐作亂，並且不斷地靠近帝國首都，艾斯德斯大人受令狩獵帝國周圍的危險種。

根據情報顯示，危險種移動的路徑預估為有向無環圖，牠們的數個巢穴坐落於地圖的末端 (也就是不會在有別的地點抵達這個地方)，而在首都前將有數個要塞，要塞正牠們的目標之地。為了阻止牠們到來，身為艾斯德斯大人的下屬，必須派軍隊前往危險種前往要塞的必經之地，即使抵達的位置無法阻止所有巢穴的危險種，但能對艾斯德斯大人貢獻一份心力便已足夠。

由於必經之地很多，好不容易在地圖上標記起來，卻又不知道哪個地點比較好 (可以阻止最多巢穴前往要塞)。正在困擾的同時，艾斯德斯大人已經將全部危險種給剷除了 …

「還沒一瞬間就將怪物解決，艾斯德斯大人啊！ <(_ _)>」

不過報告書還是得寫 …

Input

輸入有多組測資。

每組測資第一行會有一個整數 N (N < 32767)。

接下來會有 N 行，第 i 行上會有數個整數 x，直到 0 表示結束，表示有一條邊從 i 到 x。

Output

對於每組測資，輸出可以埋伏地點以及埋伏的最佳收穫情況。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
5
0
1 0
1 0
2 3 0
2 0
17
10 13 0
9 12 0
9 14 11 0
10 0
12 0
17 0
0
0
13 14 0
11 0
15 0
15 0
16 0
7 0
16 0
17 0
8 0

Sample Output

1
2
1 1
6 4

Solution

1
Read More +
解題區/解題區 - UVa

UVa 12747 - Back to Edit Distance

Problem

目標從起始序列經過操作變成目標序列。

  • 操作 1 : 任意替除掉一個元素。
  • 操作 2 : 將元素插入到任意位置。

請問最少次數為何

Sample Input

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

Sample Output

1
2
Case 1: 2
Case 2: 6

Solution

很明顯地看出，任意插入就可以直接無視，只要找有最長共同子序列即可，剩餘的元素一次替除一次插入即可。

但是最長子序列在這一題無法使用 O(n * n) 的算法，因此將其轉換成 LIS 做法，由於元素恰好不重複，可以在 O(n log n) 完成 (轉換不造成元素增加)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
// LCS to LIS
int A[262144], B[262144];
int LIS(int A[], int n) {
    vector<int> r;
    r.push_back(A[0]);
    for (int i = 1; i < n; i++) {
        int pos = (int)(upper_bound(r.begin(), r.end(), A[i]) - r.begin());
        if (pos == r.size())
            r.push_back(A[i]);
        else
            r[pos] = A[i];
    }
    return r.size();
}
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x] = i;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            B[i] = A[x];
        }
        printf("Case %d: %d\n", ++cases, (n - LIS(B, n)) * 2);
    }
    return 0;
}
/*
2
5
1 3 5 4 2
1 5 4 3 2
4
1 2 4 3
3 4 2 1
*/
Read More +
解題區/解題區 - UVa

UVa 12166 - Equilibrium Mobile

Problem

給一個天平表達式，請問至少要調整幾個權重才能使之平衡。

Sample Input

1
2
3
4
3
[[3,7],6]
40
[[2,3],[4,5]]

Sample Output

1
2
3
1
0
3

Solution

恰好是一棵二元樹，那麼可以得知道假使一個權重不改，最後的天平重量為何。
假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

藉此，可以記錄所有最後的天平重量，得知最多有多少不改 = N - 最少改變個樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
char exp[1048576];
map<long long, int> R;
void dfs(int l, int r, int dep) {
    if (exp[l] == '[') {
        int p = 0;
        for (int i = l + 1; i <= r - 1; i++) {
            if (exp[i] == '[')	p++;
            if (exp[i] == ']')	p--;
            if (p == 0 && exp[i] == ',') {
                dfs(l+1, i-1, dep+1);
                dfs(i+1, r-1, dep+1);
            }
        }
    } else {
        int w;
        exp[r+1] = '\0';
        sscanf(exp+l, "%d", &w);
        R[(long long)w<<dep]++;
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", exp);
        R.clear();
        dfs(0, strlen(exp) - 1, 0);
        int sum = 0, mx = 0;
        for (map<long long, int>::iterator it = R.begin();
            it != R.end(); it++)
            sum += it->second, mx = max(mx, it->second);
        printf("%d\n", sum - mx);
    }
    return 0;
}
/*
3
[[3,7],6]
40
[[2,3],[4,5]]
*/
Read More +
解題區/解題區 - UVa

UVa 11724 - Evaluate the Expression

Problem

每個變數皆為正整數，給定一個算術表達式和變數之間的大小關係，請問最少產生出來的答案為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0

Sample Output

1
2
3
Case 1: 4
Case 2: 9
Case 3: 4

Solution

先使用 spfa 找到根據 greedy 策略分配的變數值，如果發生負環情況直接輸出 -1。

然後使用矩陣鏈乘積的 DP 方法進行找到最小答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
char exp[1024], cond[1024];
int val[26];
int spfa(vector<int> g[]) {
    queue<int> Q;
    int inq[26] = {}, dist[26] = {};
    int cnt[26] = {};
    int u, v;
    for (int i = 0; i < 26; i++) {
        Q.push(i), dist[i] = 1;
    }
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (dist[v] < dist[u] + 1) {
                dist[v] = dist[u] + 1;
                if (!inq[v]) {
                    inq[v] = 1, Q.push(v);
                    if (++cnt[v] > 26)
                        return 0;
                }
            }
        }
    }
    for (int i = 0; i < 26; i++)
        val[i] = dist[i];
    return 1;
}
int used[512][512];
long long dp[512][512];
long long dfs(int l, int r) {
    if (used[l][r])
        return dp[l][r];
    if (l == r)
        return val[exp[l] - 'a'];
    used[l][r] = 1;
    long long &ret = dp[l][r];
    ret = 1LL<<60;
    int p = 0, test = 0;
    for (int i = l; i <= r; i++) {
        if (exp[i] == '(')	p++;
        if (exp[i] == ')')	p--;
        if (p == 0 && exp[i] == '+') {
            ret = min(ret, dfs(l, i-1) + dfs(i+1, r));
            test++;
        }
        if (p == 0 && exp[i] == '*') {
            ret = min(ret, dfs(l, i-1) * dfs(i+1, r));
            test++;
        }
    }
    if (test == 0)
        ret = min(ret, dfs(l+1, r-1));
    return ret;
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", exp);
        scanf("%d", &n);
        vector<int> g[26];
        for (int i = 0; i < n; i++) {
            scanf("%s", cond);
            g[cond[2]-'a'].push_back(cond[0]-'a');
        }
        printf("Case %d: ", ++cases);
        if(!spfa(g)) {
            puts("-1");
        } else {
            memset(used, 0, sizeof(used));
            printf("%lld\n", dfs(0, strlen(exp) - 1));
        }
    }
    return 0;
}
/*
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0
*/
Read More +
解題區/解題區 - UVa

UVa 1045 - The Great Wall Game

Problem

將棋子移動到可以形成萬里長城，也就是說移動到同一行、或同一列、或其一對角線上。

求移動得最少步數。

Sample Input

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

Sample Output

1
2
3
4
5
Board 1: 6 moves required.
  
Board 2: 0 moves required.
  
Board 3: 1 moves required.

Solution

窮舉要移動到哪裡，然後找完美匹配的最大權重 - KM 算法。

只要將移動步數弄成負權重套上去 KM 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct KM {
    int W[105][105], N;
    int mx[105], my[105]; // match arr
    int lx[105], ly[105]; // label arr
    int x[105], y[105]; // used arr
    int hungary(int nd) {
        int i;
        x[nd] = 1;
        for(i = 0; i < N; i++) {
            if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
                y[i] = 1;
                if(my[i] == -1 || hungary(my[i])) {
                    my[i] = nd;
                    return 1;
                }
            }
        }
        return 0;
    }
    int run() {
        int i, j, k, d;
        memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
        for (int i = 0; i < N; i++)
        	lx[i] = -0x3f3f3f3f, ly[i] = 0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
        for(i = 0; i < N; i++) {
            while(1) {
                memset(x, 0, sizeof(x));
                memset(y, 0, sizeof(y));
                if(hungary(i))  break;
                d = 0x3f3f3f3f;
                for(j = 0; j < N; j++) {
                    if(x[j]) {
                        for(k = 0; k < N; k++)
                            if(!y[k])
                            d = d < lx[j]+ly[k]-W[j][k] ?
                                d : lx[j]+ly[k]-W[j][k];
                    }
                }
                if(d == 0x3f3f3f3f)  break;
                for(j = 0; j < N; j++) {
                    if(x[j])    lx[j] -= d;
                    if(y[j])    ly[j] += d;
                }
            }
        }
        int res = 0;
        for(i = 0; i < N; i++) {
            if(my[i] != -1)
                res += W[my[i]][i];
        }
        return res;
    }
} km;
int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    int cases = 0;
    int n, x[105], y[105];
    while(scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
        	scanf("%d %d", &x[i], &y[i]);
        	x[i]--, y[i]--;
        }
        km.N = n;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], i, k);
        	ret = max(ret, km.run());
        }
        for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		for (int k = 0; k < n; k++)
        			km.W[j][k] = -dist(x[j], y[j], k, i);
        	ret = max(ret, km.run());
    	}
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, i);	
    	}
        ret = max(ret, km.run());
    	for (int i = 0; i < n; i++) {
        	for (int j = 0; j < n; j++)
        		km.W[j][i] = -dist(x[j], y[j], i, n - i - 1);
    	}
        ret = max(ret, km.run());
        printf("Board %d: %d moves required.\n\n", ++cases, -ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12801 - Grandpa Pepe's Pizza

Problem

現在 pizza 上有 m 個橄欖，請問是否能均分 m 塊，使得每一塊皆有一個橄欖。

Sample Input

1
2
3
4
12 3
2 8 11
12 4
4 5 7 11

Sample Output

1
2
S
N

Solution

窮舉其中兩個相鄰橄欖中的所有分割點，檢查一下即可。

稍微估價一下，點多窮舉次樹就少，點少切割成功的機率就高，所以算法總不會太差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
    int n, m, A[65536];
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < m; i++)
            scanf("%d", &A[i]);
        A[m] = A[0] + n;
        int ret = 0, div = n/m;
        for (int i = A[0]; i < A[1]; i++) {
            int d = i, ok = 1;
            for (int j = 1; j <= m; j++) {
//				printf("(%d %d] %d\n", d, d+div, A[j]);
                if (d < A[j] && A[j] <= d + div)
                    d += div;
                else {
                    ok = 0;
                    break;
                }
            }
//			puts("");
            if (ok) {
                ret = 1;
                break;
            }
        }
        puts(ret ? "S" : "N");
    }
    return 0;
}
/*
12 3
2 8 11
12 4
4 5 7 11
*/
Read More +
解題區/解題區 - UVa

UVa 12677 - Join two kingdoms

Problem

給兩棵樹，請問將兩個樹用一條邊連起來，則獲得新的一棵樹的最長路徑期望值為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4 5
1 2
2 3
4 2
2 3
3 4
4 1
4 5
1 5
1 2
2 3
3 4
4 5

Sample Output

1
2
5.350
4.400

Solution

利用 dp 方法，找到通過點 v 的 (以 v 為路徑端點)最長路徑為何，以及兩棵樹分別原有的最長路徑為何。

接著考量是否加入新一條會成為最長路徑，也就是說會通過新增加的邊。分別對每個樹的節點構成的最長路徑做排序，接著窮舉連接的點，用二分搜索找到另一個樹的節點，能夠使之成為更長的最長路徑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#define oo 0xfffffff
using namespace std;
vector<int> g[65536];
int dp_down[65536][2], dp_up[65536];
int used[65536];
void dfs(int u) {
    used[u] = 1;
    dp_down[u][0] = dp_down[u][1] = 0;
    for(int i = 0; i < g[u].size(); i++) {
    	int v = g[u][i];
        if(used[v] == 0) {
            dfs(v);
            if(dp_down[v][0]+1 > dp_down[u][1])
                dp_down[u][1] = dp_down[v][0] + 1;
            if(dp_down[u][1] > dp_down[u][0])
                swap(dp_down[u][0], dp_down[u][1]);
        }
    }
}
void dfs2(int u, int dep) {
    dp_up[u] = dep, used[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
    	int v = g[u][i];
        if(used[v] == 0) {
            int hv;
            if(dp_down[v][0] + 1 != dp_down[u][0])
                hv = dp_down[u][0];
            else
                hv = dp_down[u][1];
            hv = max(hv, dp_up[u]);
            dfs2(v, hv+1);
        }
    }
}
int main() {
    int n, m;
    int x, y;
    while (scanf("%d %d", &n, &m) == 2) {
    	int mxpath[2][65636];
        int a_diameter = 0, b_diameter = 0;
    	for (int i = 0; i <= n; i++)
    		g[i].clear();
    	for (int i = 1; i < n; i++) {
    		scanf("%d %d", &x, &y);
    		g[x].push_back(y);
    		g[y].push_back(x);
    	}
    	memset(used, 0, sizeof(used));
    	dfs(1);
    	memset(used, 0, sizeof(used));
    	dfs2(1, 0);
    	for (int i = 1; i <= n; i++) {
    		mxpath[0][i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
    		a_diameter = max(a_diameter, dp_down[i][0] + dp_down[i][1]);
    		a_diameter = max(a_diameter, dp_down[i][0] + dp_up[i]);
    	}
    		
    	for (int i = 0; i <= m; i++)
    		g[i].clear();
    	for (int i = 1; i < m; i++) {
    		scanf("%d %d", &x, &y);
    		g[x].push_back(y);
    		g[y].push_back(x);
    	}
    	memset(used, 0, sizeof(used));
    	dfs(1);
    	memset(used, 0, sizeof(used));
    	dfs2(1, 0);
        for (int i = 1; i <= m; i++) {
    		mxpath[1][i] = max(max(dp_down[i][0], dp_down[i][1]), dp_up[i]);
    		b_diameter = max(b_diameter, dp_down[i][0] + dp_down[i][1]);
    		b_diameter = max(b_diameter, dp_down[i][0] + dp_up[i]);
    	}
    	double ret = 0, suffix[65536] = {};
    	sort(mxpath[0]+1, mxpath[0]+1+n);
    	sort(mxpath[1]+1, mxpath[1]+1+m);
    	for (int i = m; i >= 0; i--)
    		suffix[i] = suffix[i+1] + mxpath[1][i];
    	int mx_diameter = max(a_diameter, b_diameter);
    	for (int i = 1, j = m; i <= n; i++) {
    		while (j > 0 && mxpath[0][i] + mxpath[1][j] >= mx_diameter)
    			j--;
    		ret += j * mx_diameter + (suffix[j + 1] + mxpath[0][i] * (m - j) + m - j);
    	}
    	printf("%.3lf\n", ret / n / m);
    }
    return 0;
}
/*
*/
Read More +
解題區/出題解題

[ACM 題目] 學姊日談

Description

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』

Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
5
1 1
5 2
3 0
0 4
4 8

Sample Output

1
2
3
4
5
1
3
1
4
12

More

名為 “學姊”。

Solution

1
Read More +