Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stdio.h>
- #include <algorithm>
- #include <fstream>
- #include <set>
- #include <cstring>
- #include <assert.h>
- #include <cstdlib>
- #include <cmath>
- #include <queue>
- using namespace std;
- typedef long long ll;
- const ll INF = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
- int n, dp[200000][2], di[200000], ans[200000];
- vector <int> g[200000], ind[200000];
- void merge (int& mx, int& sec, int a) {
- if (mx <= a) {
- sec = mx;
- mx = a;
- }
- else sec = max (sec, a);
- }
- void dp_dfs (int x, int p) {
- vector <int> v, id;
- for (int i = 0; i < g[x].size (); i++) {
- if (g[x][i] != p) {
- v.push_back (g[x][i]);
- id.push_back (ind[x][i]);
- }
- }
- g[x] = v;
- ind[x] = id;
- v.clear ();
- id.clear ();
- for (int to : g[x]) {
- dp_dfs (to, x);
- merge (dp[x][0], dp[x][1], dp[to][0] + 1);
- di[x] = max (di[to], di[x]);
- }
- di[x] = max (di[x], dp[x][0] + dp[x][1]);
- }
- void dfs (int x, int p, int mx, int di_up) {
- if (g[x].empty ()) return;
- vector <int> s[2], s_d (g[x].size ());
- s[0].resize (g[x].size ());
- s[1].resize (g[x].size ());
- s[0][g[x].size () - 1] = dp[g[x].back ()][0] + 1;
- s_d[g[x].size () - 1] = di[g[x].back ()];
- for (int i = g[x].size () - 2; i >= 0; i--) {
- int to = g[x][i];
- s[0][i] = s[0][i+1];
- s[1][i] = s[1][i+1];
- merge (s[0][i], s[1][i], dp[to][0] + 1);
- s_d[i] = max (di[to], s_d[i+1]);
- }
- int pref[2] = {0, 0}, pref_d = 0;
- for (int i = 0; i < g[x].size (); i++) {
- int to = g[x][i];
- int cur[2] = {pref[0], pref[1]}, cur_d = pref_d;
- if (i != g[x].size () - 1) {
- merge (cur[0], cur[1], s[0][i+1]);
- merge (cur[0], cur[1], s[1][i+1]);
- cur_d = max (cur_d, s_d[i+1]);
- }
- int best_diam = max (di_up, max (max (mx, cur[1]) + cur[0], cur_d));
- ans[ind[x][i]] = 1 + di[to] + best_diam;
- dfs (to, x, max (mx + 1, cur[0] + 1), best_diam);
- merge (pref[0], pref[1], dp[to][0] + 1);
- pref_d = max (pref_d, di[to]);
- }
- s[0].clear ();
- s[1].clear ();
- s_d.clear ();
- }
- int main () {
- ifstream fin ("plimbare3.in");
- ofstream fout ("plimbare3.out");
- fin >> n;
- for (int i = 0; i < n - 1; i++) {
- int u, v;
- fin >> u >> v;
- g[u-1].push_back (v - 1);
- ind[u-1].push_back (i);
- g[v-1].push_back (u - 1);
- ind[v-1].push_back (i);
- }
- dp_dfs (0, -1);
- dfs (0, -1, 0, 0);
- for (int i = 0; i < n - 1; i++)
- fout << ans[i] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement