# Road Maintenance

# Road Maintenance

+ 0 comments #include <bits/stdc++.h> using namespace std; #define pb push_back #define foreach(i,x) for(type(x)i = x.begin(); i != x.end(); i++) #define FOR(ii, aa, bb) for(int ii = aa; ii <= bb; ii++) #define type(x) __typeof(x.begin()) typedef long long ll; const int mod = (int) 1e9 + 7; const int N = 2e5 + 5; int n, m, x, y, dp[N][11][11], temp[N][11][11]; vector<int> v[N]; void dfs(int node, int root) { dp[node][0][0] = 1; foreach(it, v[node]) { if(*it == root) continue; dfs(*it, node); FOR(i, 0, 10){ FOR(j, 0, 10) { temp[node][i][j] = dp[node][i][j]; dp[node][i][j] = 0; } } FOR(i, 0, m){ FOR(j, 0, m - i){ FOR(k, 0, m){ dp[node][i + j][k] = (dp[node][i + j][k] + temp[node][i][k] * (ll) dp[*it][j][0]) % mod; dp[node][i + j][k + 1] = (dp[node][i + j][k + 1] + temp[node][i][k] * (ll) dp[*it][j][1]) % mod; if(k) dp[node][i + j + 1][k - 1] = (dp[node][i + j + 1][k - 1] + temp[node][i][k] * (ll) dp[*it][j][1] % mod * k) % mod; dp[node][i + j + 1][k] = (dp[node][i + j + 1][k] + temp[node][i][k] * (ll) dp[*it][j][1] % mod) % mod; } } } } FOR(i, 0, m) dp[node][i][1] = (dp[node][i][1] + dp[node][i][0]) % mod; } int main() { cin >> n >> m; FOR(i, 2, n) { cin >> x >> y; v[x].pb(y); v[y].pb(x); } dfs(1, 0); cout << dp[1][m][0] << endl; return 0; }

+ 0 comments The following algorithm should work in O(N) complexity. When the road link count is 10000 then the total number of roads is n/2*(n-1) = 49995000. Lets say the road numbers run from 1-49995000 or to n/2*(n-1) . Start navigating the road links. Let’s say there is a link 1-2. Assign this link the next available road number, which is one in this case. So the road lookup will get the following entries 1-(1,2) and reverse. Also the road ending in a node DS will have the following entries 1-null, 2-(1).

Let’s process link 2-3 this will add one more road, road #2. Now road look up has 2 entries, 1-(1,2), 2-(2,3). The road ending in a node DS will have the following entries 1-null, 2-(1), 3-(2). Since the start of this link node 2 has an entry in road ending in a node DS, so road 1 will be joined with road 2 to form a new road #3. Now road lookup has one more entry 3-(1,3). Also since this road ends in road #3 the corresponding entry in road ending in a node DS is updates to 3-(2,3). Also the road parts DS will have one entry now, 3-(1,2). This DS stores a link for all the single road parts for this road. The entry for road 2 in road ending in a node DS will also get updated 2-(1,2)

We introduce one more DS here, road grouping. This DS will store the list of all the road with which the given road has at-least one common road, and hence are connected. At this point the DS will have the following entries. 1-(3), 2-(3), 3-(1,2). As you can see the entries in this DS are symmetrical. What this means that road #1 can be paired with 2. So one one pair of disconnected road is possible among the three roads. Lets process link 2-4. This will add one more road road #3. Now road look up has fourth entry 4-(2,4). The road ending in a node DS has one more entry 4-(4). Since the start of this road road #2 has an entry in this DS which point to 2 roads ending in #2 i.e road #1,2. These first roads will combine with road 4 and form a new road, road #5. The road look up will have the new entries as 5-(1,4) and 6-(3,4). The road parts DS will have a new entry for 5-(1,4). The road grouping will be updated with a blank entry for 4-null. The entry for 5 will be 5-(1,3,4), the following entries will be updated to 1-(3,5), 3-(1,2,5),4-(5).

The second road will combine with 4 to form road #6. The road look up will have the new entry as 6-(3,4). The entry for 6 in road parts will be 6-(2,4). The entry for 6 in road grouping will be 6-(2,3,4,5), the following entries will be updated to 2-(3,6), 3-(1,2,5, 6), 4-(5, 6), 5-(1,3,4,6)

Following will be the entries in road grouping 1-(3,5), 2-(3,6), 3-(1,2,5,6),4-(5,6),5-(1,3,4,6), (2,3,4,5). So from single road entries of 3, 2 can be selected in 3 ways. Road 3 can paired with 4. Road 5 can be paired with 2. Road 6 can be paired with with road 1. So a total of 6 possibilities.

+ 1 comment The problem is not clear. Can you please reword or elaborate?

+ 0 comments Okay, I had a really hard time trying to understand the sample input, and on reading bretvh's discussion, I have understood it. It seems that people could not understand, and so I will try to explain it to people so they get what you are supposed to do.

The first is pretty clear...He does [1,2] and then does [2,3], which does NOT have any path in common.

Now, for the example [1,2], and [3,4], this is what happens.

He does [1,2].

He then teleports to the city 3. From city 3, he maintains [3,2] AND [2,4]. These two add up to [3,4].

So, he has done [1,2] and [3,4] without any path being repeated. This is thus counted in the total

+ 1 comment I do not understand this problem, could someone please help me understand it. First, problem statement indicates that for N cities there are N -1 bidirectional roads. In the explanation of the sample problem there are N cities and 6 possible "routes"(a term which is undefined) using, what to me looks like more than N-1 roads, perhaps some are roads and some are paths or perhaps they are routes... the problem also states that there is guaranteed that there is a path from any city to any other city...and that a path is one or more connected roads...Ok. The given roads, in the sample problem, are [1,2], [2,3], [2,4] which are bidirectional roads. We have a constraint that says a path cannot contain the two same roads(I assume this means [1,2] + [2,1] is invalid) so I assume we have paths: [1,2], [2,1], [2,3], [3,2], [2,4], [4,2], [1,2]+[2,3], [1,2]+[2,4], [3,2]+[2,4], [3,2]+[2,1], [4,2]+[2,1], [4,2]+[2,3] and they satisfy the constraint that there is a path from any city to any other city...so the explanation claims that there is a route [1,2]+[3,4] but it does not appear connected and and to go [1,2]+[2,3]+[3,2]+[2,4] violates the constraint that a path cannot contain the same two roads...perhaps a route is one or more paths and is not subject to the constraint of a path?? is that the case? BUT here is the kicker!!! You need M paths not M routes...so what am I missing? Are the 6 routes discussed [1,2],[1,3],[1,4],[2,3],[2,4],[3,4] or are they roads?? and can they be used as paths to construct other paths?? and why are available to use? confusing. Finally, why not [1,3]+[3,4]??

No more comments

Sort 5 Discussions, By:

Please Login in order to post a comment