CF1413F. Roads and Ramen

Solution

感覺這個套路也見過許多次了？大概這種奇奇怪怪的樹上最長路徑的題都得往直徑靠一靠。

大概有個結論是：存在一個最優路徑使得其起始點和直徑起始點有交。

然后我們只需要求出一個直徑的起始點$A,B$，分別維護以$A,B$為根的樹到其他點的邊權異或和以及最長路徑，上線段樹就行了。

時間復雜度$O(n+q\log n)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 60; const int mods = 1e9 + 7; const int inv2 = (mods + 1) >> 1; const int MAXN = 2005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); !isalpha(c) && c != EOF; c = gc());}inline void reads(char *st) {char c;int n = 0;getc(st[++ n]);for (c = gc(); isalpha(c) ; c = gc()) st[++ n] = c;st[n + 1] = '\0';}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: reads; using FastIO :: print;PR E[MAXN]; vector<PR> e[MAXN]; int id[MAXN], dfnA[MAXN], dfnB[MAXN], dep[MAXN], depA[MAXN], depB[MAXN], fnsA[MAXN], fnsB[MAXN], col[MAXN], MX, ID, DFN = 0, A, B;void dfsA(int x, int father) {id[dfnA[x] = ++ DFN] = x;if (dep[x] > MX) MX = dep[x], ID = x;for (auto v : e[x]) {if (v.fi == father) continue;col[v.fi] = col[x] ^ v.se, dep[v.fi] = dep[x] + 1, dfsA(v.fi, x);}fnsA[x] = DFN; } void dfsB(int x, int father) {id[dfnB[x] = ++ DFN] = x;if (dep[x] > MX) MX = dep[x], ID = x;for (auto v : e[x]) {if (v.fi == father) continue;col[v.fi] = col[x] ^ v.se, dep[v.fi] = dep[x] + 1, dfsB(v.fi, x);}fnsB[x] = DFN; }struct Segment_Tree {int tag[MAXN << 2], s[MAXN << 2][2];void down(int x) {if (tag[x]) {tag[x << 1] ^= 1, swap(s[x << 1][0], s[x << 1][1]);tag[x << 1 | 1] ^= 1, swap(s[x << 1 | 1][0], s[x << 1 | 1][1]);tag[x] = 0;}}void up(int x) {s[x][0] = max(s[x << 1][0], s[x << 1 | 1][0]);s[x][1] = max(s[x << 1][1], s[x << 1 | 1][1]);}void build(int x, int l, int r) {if (l == r) {s[x][col[id[l]]] = dep[id[l]];s[x][col[id[l]] ^ 1] = -INF;return;}int mid = (l + r) >> 1;build(x << 1, l, mid);build(x << 1 | 1, mid + 1, r);up(x);}void update(int x, int l, int r, int L, int R) {if (l >= L && r <= R) {tag[x] ^= 1;swap(s[x][0], s[x][1]);return;}down(x);int mid = (l + r) >> 1;if (R <= mid) update(x << 1, l, mid, L, R);else if (L > mid) update(x << 1 | 1, mid + 1, r, L, R);else update(x << 1, l, mid, L, mid), update(x << 1 | 1, mid + 1, r, mid + 1, R);up(x);}void print(int x, int l, int r) {if (l == r) { cout << id[l] << ":" << s[x][0] << endl; return; }int mid = (l + r) >> 1;down(x);print(x << 1, l, mid);print(x << 1 | 1, mid + 1, r);} } TA, TB; signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifint n;read(n);for (int i = 1, u, v, c; i < n ; ++ i) {read(u), read(v), read(c);e[u].PB(MP(v, c));e[v].PB(MP(u, c));E[i] = MP(u, v);}DFN = MX = ID = col[1] = dep[1] = 0, dfsA(1, 0), A = ID;DFN = MX = ID = col[A] = dep[A] = 0, dfsA(A, 0), B = ID;TA.build(1, 1, n);for (int i = 1; i <= n ; ++ i) depA[i] = dep[i];DFN = MX = ID = col[B] = dep[B] = 0, dfsB(B, 0);TB.build(1, 1, n);for (int i = 1; i <= n ; ++ i) depB[i] = dep[i];int Case;read(Case);while (Case --) {int x;read(x);int u = E[x].fi, v = E[x].se;if (depA[u] < depA[v]) swap(u, v);TA.update(1, 1, n, dfnA[u], fnsA[u]);if (depB[u] < depB[v]) swap(u, v);TB.update(1, 1, n, dfnB[u], fnsB[u]);print(max(TA.s[1][0], TB.s[1][0])), putc('\n');}return 0; }

總結

以上是生活随笔為你收集整理的CF1413F. Roads and Ramen(树的直径，线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。