We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Trees
- Tree Coordinates
- Discussions
Tree Coordinates
Tree Coordinates
Sort by
recency
|
21 Discussions
|
Please Login in order to post a comment
"Cleaning: Transforming Chaos to Calm. Discover the profound impact of a tidy space in just 30 words."Cleaning From clarity of mind to enhanced productivity, cleanliness cultivates harmony and well-being."
I hope I'm not missing something, but 2nd example provided provides edge graph with vertex labeling doesn't appear correct. Usually when I've worked edge and vertex graphs via graph there is a correspondence between vertex labeling and vertex position (save using modulus on vertex indexing to fit example...). The example provided has index listing out of range to points array, so I am a bit confused on vertex index labeling incidentally relative points provided.
Okay, it's already too dark here!
`
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
using namespace std;
define all(a) (a).begin(), (a).end()
define sz(a) static_cast((a).size())
define FOR(i, a, b) for (int i(a), b_(b); i < b_; ++i)
define REP(i, n) FOR (i, 0, n)
define FORD(i, a, b) for (int i(a), b_(b); i >= b_; --i)
define UNIQUE(a) sort(all(a)), (a).erase(unique(all(a)), (a).end())
define CL(a, v) memset(a, v, sizeof a)
define eb emplace_back
define pb push_back
define X first
define Y second
typedef long long ll; typedef long double ld; typedef vector vi; typedef pair pii; template using min_queue = priority_queue, greater>;
const int INF = static_cast(1e9); const long long INF_LL = static_cast(4e18); const double pi = acos(-1.0);
template inline T& smin(T& x, const T& y) { return x > y ? x = y : x; } template inline T& smax(T& x, const T& y) { return x < y ? x = y : x; } template inline T sqr(const T& x) { return x * x; } template inline int sgn(const T& x) { return (T(0) < x) - (x < T(0)); }
template T gcd(T a, T b) { for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a); return a + b; }
using uint = unsigned int; // Buffer size should be 2^12 or 2^13 for optimal performance with files. const uint BUFFER_SIZE = 1 << 12; // Maximum possible length of a string representing primitive type // assuming we won't encounter huge double values. const uint MAX_LENGTH = 1 << 7;
namespace Detail { struct Width { uint value; }; struct Fill { char value; }; struct Base { uint value; }; struct Precision { uint value; }; struct Delimiter { const char* value; }; } // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; } Detail::Fill setFill(char value = ' ') { return {value}; } Detail::Base setBase(uint value = 10) { assert(2 <= value && value <= 36); return {value}; } Detail::Precision setPrecision(uint value = 9) { assert(value < MAX_LENGTH); return {value}; } Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
/*********************************************** input classes ************************************************/ class InputDevice { protected: const char* head; const char* tail;
InputDevice(const char* head, const char* tail) : head(head), tail(tail), base(setBase().value) {} InputDevice(InputDevice const&) = delete; InputDevice& operator = (InputDevice const&) = delete;
virtual void fillInput() = 0;
inline char nextChar() { if (__builtin_expect(head >= tail, false)) fillInput(); return *head++; }
template int readUnsignedIntGeneral(I& arg, char c) { I value = 0; int length = 0; for (;; ++length, c = nextChar()) { if (isDigit(c)) c -= '0'; else if (isUpper(c)) c -= 'A' - 10; else if (isLower(c)) c -= 'a' - 10; else c = base; if (c >= base) break; value = base * value + c; } arg = value; return --head, length; }
template inline int readUnsignedInt(I& arg, char c) { if (__builtin_expect(base > 10, false)) return readUnsignedIntGeneral(arg, c); I value = 0; int length = 0; for (; static_cast(c - '0') < base; ++length, c = nextChar()) value = base * value + c - '0'; arg = value; return --head, length; }
template inline bool readSignedInt(I& arg, char c) { bool negative = c == '-'; if (negative) c = nextChar(); typename make_unsigned::type unsignedArg; if (readUnsignedInt(unsignedArg, c) == 0) return false; arg = negative ? ~static_cast(unsignedArg - 1) : static_cast(unsignedArg); return true; }
template bool readFloatingPoint(F& arg, char c) { bool negative = c == '-'; if (negative) c = nextChar(); unsigned long long integerPart; if (readUnsignedInt(integerPart, c) == 0) return false; arg = static_cast(integerPart); if (nextChar() == '.') { unsigned long long fractionalPart = 0; int fractionalLength = readUnsignedInt(fractionalPart, nextChar()); if (fractionalLength > 0) { unsigned long long basePower = 1; for (; fractionalLength; --fractionalLength) basePower *= base; arg += static_cast(fractionalPart) / basePower; } } else --head; if (negative) arg = -arg; return true; }
public: static inline bool isSpace(char c) { return static_cast(c - '\t') < 5 || c == ' '; } static inline bool isDigit(char c) { return static_cast(c - '0') < 10; } static inline bool isUpper(char c) { return static_cast(c - 'A') < 26; } static inline bool isLower(char c) { return static_cast(c - 'a') < 26; } static inline bool isOneOf(char c, const char* str) { return strchr(str, c) != nullptr; }
uint base; void putBack() { --head; } // can be called only once directly after successfully reading a character
inline bool readChar(char& arg) { if (__builtin_expect(head >= tail, false)) { fillInput(); if (__builtin_expect(head >= tail, false)) return arg = '\0', false; } return arg = *head++, true; }
template inline char skipCharacters(UnaryPredicate isSkipped) { char c; do { c = nextChar(); } while (isSkipped(c)); return c; } inline char skipCharacters() { return skipCharacters(isSpace); }
template inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) { skipCharacters(isTerminator); // put back first non-skipped character, reserve space for null character for (--head, --limit; head < tail; fillInput()) { ptrdiff_t chunkSize = find_if(head, min(tail, head + limit), isTerminator) - head; arg = copy_n(head, chunkSize, arg); head += chunkSize; limit -= chunkSize; if (chunkSize == 0 || head < tail) break; } return *arg = '\0', true; }
template inline bool readUnsignedInt(I& arg) { return readUnsignedInt(arg, skipCharacters()) > 0; } template inline bool readSignedInt(I& arg) { return readSignedInt(arg, skipCharacters()); } template inline bool readFloatingPoint(F& arg) { return readFloatingPoint(arg, skipCharacters()); } };
class InputFile : public InputDevice { FILE* file; bool lineBuffered; bool owner; char buffer[BUFFER_SIZE];
void fillInput() override { head = buffer; *buffer = '\0'; if (__builtin_expect(!lineBuffered, true)) { tail = head + fread(buffer, 1, BUFFER_SIZE, file); } else { tail = head; if (fgets(buffer, BUFFER_SIZE, file)) while (*tail) ++tail; } }
public: InputFile(FILE* file = stdin, bool lineBuffered = true, bool takeOwnership = false) : InputDevice(buffer, buffer) , file(file), lineBuffered(lineBuffered), owner(takeOwnership) {} InputFile(const char* fileName) : InputFile(fopen(fileName, "r"), false, true) {} ~InputFile() { if (owner) fclose(file); } };
// Picks up data appended to the string but doesn't handle reallocation. class InputString : public InputDevice { void fillInput() override { while (*tail) ++tail; }
public: InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {} InputString(const char* s) : InputDevice(s, s + strlen(s)) {} };
/*********************************************** output classes ***********************************************/ class OutputDevice { protected: char buffer[BUFFER_SIZE + MAX_LENGTH]; char* output; char* end; bool separate;
OutputDevice() : output(buffer), end(buffer + BUFFER_SIZE + MAX_LENGTH), separate(false), width(setWidth().value) , fill(setFill().value), base(setBase().value), precision(setPrecision().value), delimiter(setDelimiter().value) {} OutputDevice(OutputDevice const&) = delete; OutputDevice& operator = (OutputDevice const&) = delete;
virtual void writeToDevice(uint count) = 0;
inline void flushMaybe() { if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) { writeToDevice(BUFFER_SIZE); output = copy(buffer + BUFFER_SIZE, output, buffer); } }
template inline char* writeUnsignedInt(I arg, char* last) { if (__builtin_expect(arg == 0, false)) *--last = '0'; if (__builtin_expect(base == 10, true)) { for (; arg; arg /= 10) *--last = '0' + arg % 10; } else for (; arg; arg /= base) { I digit = arg % base; *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit; } return last; }
template inline char* writeSignedInt(I arg, char* last) { auto unsignedArg = static_cast::type>(arg); if (arg < 0) { last = writeUnsignedInt(~unsignedArg + 1, last); *--last = '-'; return last; } return writeUnsignedInt(unsignedArg, last); }
template char* writeFloatingPoint(F arg, char* last) { bool negative = signbit(arg); if (negative) arg = -arg; if (isnan(arg)) for (int i = 0; i < 3; ++i) *--last = i["NaN"]; else if (isinf(arg)) for (int i = 0; i < 3; ++i) *--last = i["fnI"]; else { auto integerPart = static_cast(arg); arg -= integerPart; for (int i = 0; i < precision; ++i) arg *= base; auto fractionalPart = static_cast(arg); if ((arg - fractionalPart) * 2 >= static_cast(1)) { if (precision == 0) ++integerPart; else ++fractionalPart; } if (precision > 0) { char* point = last - precision; last = writeUnsignedInt(fractionalPart, last); ::fill(point, last, '0'); last = point; *--last = '.'; } last = writeUnsignedInt(integerPart, last); } if (negative) *--last = '-'; return last; }
inline int writeT(char* first) { int delimiterLenght = separate ? writeDelimiter() : 0; separate = true; int charsWritten = static_cast(end - first); if (__builtin_expect(charsWritten < width, false)) charsWritten += writeFill(width - charsWritten); output = copy(first, end, output); flushMaybe(); return delimiterLenght + charsWritten; }
inline int writeFill(int count) { int result = count; if (__builtin_expect(output + count + MAX_LENGTH < end, true)) { if (count == 1) *output++ = fill; else output = fill_n(output, count, fill); } else for (uint chunkSize = static_cast(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) { if (chunkSize > count) chunkSize = count; output = fill_n(output, chunkSize, fill); flushMaybe(); if ((count -= chunkSize) == 0) break; } return result; }
public: int width; char fill; uint base; uint precision; string delimiter;
inline int writeChar(char arg) { separate = false; *output++ = arg; flushMaybe(); return 1; }
inline int writeString(const char* arg, int count, bool checkWidth = true) { separate = false; int result = count + (checkWidth && count < width ? writeFill(width - count) : 0); if (__builtin_expect(output + count + MAX_LENGTH < end, true)) { if (count == 1) *output++ = *arg; else output = copy_n(arg, count, output); } else for (int chunkSize = static_cast(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) { if (chunkSize > count) chunkSize = count; output = copy_n(arg, chunkSize, output); flushMaybe(); if ((count -= chunkSize) == 0) break; arg += chunkSize; } return result; }
inline int writeDelimiter() { return writeString(delimiter.c_str(), static_cast(delimiter.size()), false); }
template inline int writeUnsignedInt(I arg) { return writeT(writeUnsignedInt(arg, end)); } template inline int writeSignedInt(I arg) { return writeT(writeSignedInt(arg, end)); } template inline int writeFloatingPoint(F arg) { return writeT(writeFloatingPoint(arg, end)); }
inline void flush() { writeToDevice(static_cast(output - buffer)); output = buffer; } virtual ~OutputDevice() {}; };
class OutputFile : public OutputDevice { FILE* file; bool owner;
void writeToDevice(uint count) override { fwrite(buffer, 1, count, file); fflush(file); }
public: OutputFile(FILE* file = stdout, bool takeOwnership = false) : file(file), owner(takeOwnership) {} OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {} ~OutputFile() override { flush(); if (owner) fclose(file); } };
class OutputString : public OutputDevice { string& str;
void writeToDevice(uint count) override { str.append(buffer, count); }
public: OutputString(string& str) : OutputDevice(), str(str) {} ~OutputString() override { flush(); } };
/************************************************ read & write ************************************************/ //unique_ptr input; unique_ptr input; //unique_ptr output; unique_ptr output;
// property setters inline int read(Detail::Base base) { input->base = base.value; return 0; } // primitive types inline int read() { return 0; } inline int read(char& arg) { return input->readChar(arg); } template inline typename enable_if::value && is_unsigned::value, int>::type read(I& arg) { return input->readUnsignedInt(arg); } template inline typename enable_if::value && is_signed::value, int>::type read(I& arg) { return input->readSignedInt(arg); } template inline typename enable_if::value, int>::type read(F& arg) { return input->readFloatingPoint(arg); } // characters skip inline int read(const char& arg) { input->skipCharacters([arg](char c) { return arg != c; }); return 0; } inline int read(const char* arg) { if (*arg) input->skipCharacters([arg](char c) { return InputDevice::isOneOf(c, arg); }); else input->skipCharacters(); input->putBack(); return 0; } inline int read(bool (isSkipped)(char)) { input->skipCharacters(isSkipped); input->putBack(); return 0; } // forward declarations so everything compiles template int read(char arg, int limit, bool (isTerminator)(char), Ts&&... args); template int read(char arg, int limit, const char* terminators, Ts&&... args); template ())> int read(Iterator first, Iterator last, Ts&&... args); template ())> int read(Iterator first, int count, Ts&&... args); template ::value, void>::type> int read(T&& arg1, Ts&&... args); // C strings inline int read(char* arg, int limit, const char* terminators = "") { if (!terminators) return input->readString(arg, limit, InputDevice::isSpace); else return input->readString(arg, limit, [terminators](char c) { return InputDevice::isOneOf(c, terminators); }); } template inline int read(char first, char* last, Ts&&... args) { return read(first, static_cast(last - first), forward(args)...); } template inline int read(char (&arg)[N], Ts&&... args) { return read(static_cast(arg), N, forward(args)...); } template inline int read(char* arg, int limit, bool (isTerminator)(char), Ts&&... args) { int argsRead = input->readString(arg, limit, isTerminator); return argsRead + read(forward(args)...); } template inline int read(char arg, int limit, const char* terminators, Ts&&... args) { int argsRead = read(arg, limit, terminators); return argsRead + read(forward(args)...); } // complex types and ranges template inline int read(pair& arg) { return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0; } template inline int read(vector& arg) { uint n; if (read(n) == 0) return 0; arg.resize(n); return read(arg.begin(), arg.end()); } template int read(Iterator first, Iterator last, Ts&&... args) { int success = 1; for (; first != last; ++first) success &= read(*first); return success + read(forward(args)...); } template int read(Iterator first, int count, Ts&&... args) { return read(first, first + count, forward(args)...); } template inline int read(T&& arg1, Ts&&... args) { int argsRead = read(forward(arg1)); return argsRead + read(forward(args)...); }
// property setters inline int write(Detail::Width width) { output->width = static_cast(width.value); return 0; } inline int write(Detail::Fill fill) { output->fill = fill.value; return 0; } inline int write(Detail::Base base) { output->base = base.value; return 0; } inline int write(Detail::Precision precision) { output->precision = precision.value; return 0; } inline int write(Detail::Delimiter delimiter) { output->delimiter = delimiter.value; return 0; } // primitive types inline int write() { return 0; } inline int write(char arg) { return output->writeChar(arg); } template inline typename enable_if::value && is_unsigned::value, int>::type write(I arg) { return output->writeUnsignedInt(arg); } template inline typename enable_if::value && is_signed::value, int>::type write(I arg) { return output->writeSignedInt(arg); } template inline typename enable_if::value, int>::type write(F arg) { return output->writeFloatingPoint(arg); } // complex types inline int write(const char* arg) { return output->writeString(arg, static_cast(strlen(arg))); } template inline int write(char (&arg)[N]) { return output->writeString(arg, static_cast(strlen(arg))); } inline int write(const string& arg) { return output->writeString(arg.c_str(), static_cast(arg.size())); } template inline int write(const pair& arg) { int charsWritten = write(arg.first); charsWritten += output->writeDelimiter(); return charsWritten + write(arg.second); } // forward declarations so everything compiles template ::value, decltype(*std::declval())>::type> int write(Iterator first, Iterator last, Ts&&... args); template ::value, decltype(*std::declval())>::type> int write(Iterator first, int count, Ts&&... args); template int write(T&& arg, T2&& arg2, Ts&&... args); // ranges template int write(Iterator first, Iterator last, Ts&&... args) { int charsWritten = 0; for (; first != last; charsWritten += ++first == last ? 0 : output->writeDelimiter()) charsWritten += write(*first); return charsWritten + write(forward(args)...); } template int write(Iterator first, int count, Ts&&... args) { return write(first, first + count, forward(args)...); } template inline int write(T&& arg, T2&& arg2, Ts&&... args) { int charsWritten = write(forward(arg)); return charsWritten + write(forward(arg2), forward(args)...); } template inline int writeln(Ts&&... args) { return write(forward(args)..., '\n'); }
void flush() { output->flush(); }
template class GraphUL { int n, m; vector adjacent[V];
public: GraphUL(int newn = 0, int newm = -1) : n(0) { init(newn, newm); }
void init(int newn, int newm = -1) { for (int i = 0; i < n; ++i) vector().swap(adjacent[i]); n = newn; m = newm >= 0 ? newm : n; }
void addEdge(int u, int v) { assert(u < n && v < m); adjacent[u].push_back(v); if (!ORIENTED && u != v) adjacent[v].push_back(u); }
bool oriented() const { return ORIENTED; } int size() const { return n; } int size2() const { return m; } const vector& operator [] (int v) const { return adjacent[v]; } };
template class SegmentTree { int n; vector tree;
public: SegmentTree(int newn = 0) { init(newn); } void init(int newn) { n = newn; vector(2*n).swap(tree); }
int size() const { return n; } T& operator [] (int i) { return tree[i + n]; } const T& operator [] (int i) const { return tree[i + n]; }
void build() { for (int i = n; --i; ) tree[i] = combine(tree[i<<1], tree[i<<1|1]); }
void set(int i, const T& value) { for (tree[i += n] = value; i >>= 1; ) tree[i] = combine(tree[i<<1], tree[i<<1|1]); }
void add(int i, const T& delta) { assert(COMMUTATIVE); for (i += n; i; i >>= 1) tree[i].add(delta); }
T query(int l, int r) const { // [l, r) T resl = T(), resr = T(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) if (COMMUTATIVE) { if (l&1) resl.add(tree[l++]); if (r&1) resr.add(tree[--r]); } else { if (l&1) resl = combine(resl, tree[l++]); if (r&1) resr = combine(tree[--r], resr); } return combine(resl, resr); } };
template struct Tmax { T value; Tmax(const T& value = -numeric_limits::max()) : value(value) {} inline operator T() const { return value; } inline void add(const Tmax& other) { smax(value, other.value); } friend inline Tmax combine(const Tmax& lhs, const Tmax& rhs) { return max(lhs.value, rhs.value); } }; namespace std { template struct numeric_limits> { constexpr static T max() { return numeric_limits::max(); } }; }
template class LCA { public: int i, treePos; int root[V], depth[V+1], pos[V];
struct Imin { static int* data; int index; Imin(int index = V) : index(index) {} operator int() const { return index; } void add(const Imin& other) { if (data[other] < data[index]) index = other; } friend Imin combine(const Imin& lhs, const Imin& rhs) { return data[rhs] < data[lhs] ? rhs : lhs; } }; SegmentTree tree;
template void dfs(const G& graph, int v) { root[v] = i; pos[v] = treePos; tree[treePos++] = v; for (int u : graph[v]) if (pos[u] == -1) { depth[u] = depth[v] + 1; dfs(graph, u); tree[treePos++] = v; } }
template void build(const G& graph) { depth[V] = V; int n = graph.size(); treePos = 0; fill_n(pos, n, -1); tree.init(2 * n - 1); for (i = 0; i < n; ++i) if (pos[i] == -1) { depth[i] = 0; dfs(graph, i); } Imin::data = depth; tree.build(); }
int lca(int u, int v) { if (root[u] != root[v]) return -1; if (pos[u] > pos[v]) swap(u, v); Imin::data = depth; return tree.query(pos[u], pos[v] + 1).index; } }; template int* LCA::Imin::data;
const int N = 75e3+3; int n, m; GraphUL graph; LCA lca;
pii p[N], l[N]; int sum[N]; int o[N];
int main() {
ifdef LocalHost
input.reset(new InputFile("input.txt")); //input.reset(new InputFile()); output.reset(new OutputFile()); //output.reset(new OutputFile("output2.txt"));
else
input.reset(new InputFile(stdin, false)); //input.reset(new InputFile()); output.reset(new OutputFile());
endif
read(n, m); graph.init(n); REP(i, n-1) { int u, v; read(u, v); --u; --v; graph.addEdge(u, v); } lca.build(graph);
read(p, m); int h = 0; REP(i, m) { --p[i].X; --p[i].Y; sum[i] = lca.depth[p[i].X] + lca.depth[p[i].Y]; if (sum[i] > sum[h]) h = i; }
REP(i, m) { l[i].X = lca.depth[lca.lca(p[i].X, p[h].X)]; l[i].Y = lca.depth[lca.lca(p[i].Y, p[h].Y)]; o[i] = i; } sort(o, o + m, [](int i, int j) { return l[i].X > l[j].X || (l[i].X == l[j].X && l[i].Y < l[j].Y); });
SegmentTree> tree(l[h].Y+1); int ans = 0; REP(i, m) { int j = o[i]; int t = tree.query(0, l[j].Y+1); if (t >= -2*n) smax(ans, sum[j] - 2 * l[j].X + t); if (i > 0) smax(ans, sum[h] + sum[j] - 2 * (l[j].X + l[j].Y)); tree.add(l[j].Y, sum[j] - 2 * l[j].Y); } writeln(ans);
ifdef LocalHost
flush(); cerr << endl << endl << static_cast(clock()) / CLOCKS_PER_SEC << endl; `
endif
return 0; }
`#include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
include
using namespace std;
define all(a) (a).begin(), (a).end()
define sz(a) static_cast((a).size())
define FOR(i, a, b) for (int i(a), b_(b); i < b_; ++i)
define REP(i, n) FOR (i, 0, n)
define FORD(i, a, b) for (int i(a), b_(b); i >= b_; --i)
define UNIQUE(a) sort(all(a)), (a).erase(unique(all(a)), (a).end())
define CL(a, v) memset(a, v, sizeof a)
define eb emplace_back
define pb push_back
define X first
define Y second
typedef long long ll; typedef long double ld; typedef vector vi; typedef pair pii; template using min_queue = priority_queue, greater>;
const int INF = static_cast(1e9); const long long INF_LL = static_cast(4e18); const double pi = acos(-1.0);
template inline T& smin(T& x, const T& y) { return x > y ? x = y : x; } template inline T& smax(T& x, const T& y) { return x < y ? x = y : x; } template inline T sqr(const T& x) { return x * x; } template inline int sgn(const T& x) { return (T(0) < x) - (x < T(0)); }
template T gcd(T a, T b) { for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a); return a + b; }
using uint = unsigned int; // Buffer size should be 2^12 or 2^13 for optimal performance with files. const uint BUFFER_SIZE = 1 << 12; // Maximum possible length of a string representing primitive type // assuming we won't encounter huge double values. const uint MAX_LENGTH = 1 << 7;
namespace Detail { struct Width { uint value; }; struct Fill { char value; }; struct Base { uint value; }; struct Precision { uint value; }; struct Delimiter { const char* value; }; } // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; } Detail::Fill setFill(char value = ' ') { return {value}; } Detail::Base setBase(uint value = 10) { assert(2 <= value && value <= 36); return {value}; } Detail::Precision setPrecision(uint value = 9) { assert(value < MAX_LENGTH); return {value}; } Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
/*********************************************** input classes ************************************************/ class InputDevice { protected: const char* head; const char* tail;
InputDevice(const char* head, const char* tail) : head(head), tail(tail), base(setBase().value) {} InputDevice(InputDevice const&) = delete; InputDevice& operator = (InputDevice const&) = delete;
virtual void fillInput() = 0;
inline char nextChar() { if (__builtin_expect(head >= tail, false)) fillInput(); return *head++; }
template int readUnsignedIntGeneral(I& arg, char c) { I value = 0; int length = 0; for (;; ++length, c = nextChar()) { if (isDigit(c)) c -= '0'; else if (isUpper(c)) c -= 'A' - 10; else if (isLower(c)) c -= 'a' - 10; else c = base; if (c >= base) break; value = base * value + c; } arg = value; return --head, length; }
template inline int readUnsignedInt(I& arg, char c) { if (__builtin_expect(base > 10, false)) return readUnsignedIntGeneral(arg, c); I value = 0; int length = 0; for (; static_cast(c - '0') < base; ++length, c = nextChar()) value = base * value + c - '0'; arg = value; return --head, length; }
template inline bool readSignedInt(I& arg, char c) { bool negative = c == '-'; if (negative) c = nextChar(); typename make_unsigned::type unsignedArg; if (readUnsignedInt(unsignedArg, c) == 0) return false; arg = negative ? ~static_cast(unsignedArg - 1) : static_cast(unsignedArg); return true; }
template bool readFloatingPoint(F& arg, char c) { bool negative = c == '-'; if (negative) c = nextChar(); unsigned long long integerPart; if (readUnsignedInt(integerPart, c) == 0) return false; arg = static_cast(integerPart); if (nextChar() == '.') { unsigned long long fractionalPart = 0; int fractionalLength = readUnsignedInt(fractionalPart, nextChar()); if (fractionalLength > 0) { unsigned long long basePower = 1; for (; fractionalLength; --fractionalLength) basePower *= base; arg += static_cast(fractionalPart) / basePower; } } else --head; if (negative) arg = -arg; return true; }
public: static inline bool isSpace(char c) { return static_cast(c - '\t') < 5 || c == ' '; } static inline bool isDigit(char c) { return static_cast(c - '0') < 10; } static inline bool isUpper(char c) { return static_cast(c - 'A') < 26; } static inline bool isLower(char c) { return static_cast(c - 'a') < 26; } static inline bool isOneOf(char c, const char* str) { return strchr(str, c) != nullptr; }
uint base; void putBack() { --head; } // can be called only once directly after successfully reading a character
inline bool readChar(char& arg) { if (__builtin_expect(head >= tail, false)) { fillInput(); if (__builtin_expect(head >= tail, false)) return arg = '\0', false; } return arg = *head++, true; }
template inline char skipCharacters(UnaryPredicate isSkipped) { char c; do { c = nextChar(); } while (isSkipped(c)); return c; } inline char skipCharacters() { return skipCharacters(isSpace); }
template inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) { skipCharacters(isTerminator); // put back first non-skipped character, reserve space for null character for (--head, --limit; head < tail; fillInput()) { ptrdiff_t chunkSize = find_if(head, min(tail, head + limit), isTerminator) - head; arg = copy_n(head, chunkSize, arg); head += chunkSize; limit -= chunkSize; if (chunkSize == 0 || head < tail) break; } return *arg = '\0', true; }
template inline bool readUnsignedInt(I& arg) { return readUnsignedInt(arg, skipCharacters()) > 0; } template inline bool readSignedInt(I& arg) { return readSignedInt(arg, skipCharacters()); } template inline bool readFloatingPoint(F& arg) { return readFloatingPoint(arg, skipCharacters()); } };
class InputFile : public InputDevice { FILE* file; bool lineBuffered; bool owner; char buffer[BUFFER_SIZE];
void fillInput() override { head = buffer; *buffer = '\0'; if (__builtin_expect(!lineBuffered, true)) { tail = head + fread(buffer, 1, BUFFER_SIZE, file); } else { tail = head; if (fgets(buffer, BUFFER_SIZE, file)) while (*tail) ++tail; } }
public: InputFile(FILE* file = stdin, bool lineBuffered = true, bool takeOwnership = false) : InputDevice(buffer, buffer) , file(file), lineBuffered(lineBuffered), owner(takeOwnership) {} InputFile(const char* fileName) : InputFile(fopen(fileName, "r"), false, true) {} ~InputFile() { if (owner) fclose(file); } };
// Picks up data appended to the string but doesn't handle reallocation. class InputString : public InputDevice { void fillInput() override { while (*tail) ++tail; }
public: InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {} InputString(const char* s) : InputDevice(s, s + strlen(s)) {} };
/*********************************************** output classes ***********************************************/ class OutputDevice { protected: char buffer[BUFFER_SIZE + MAX_LENGTH]; char* output; char* end; bool separate;
OutputDevice() : output(buffer), end(buffer + BUFFER_SIZE + MAX_LENGTH), separate(false), width(setWidth().value) , fill(setFill().value), base(setBase().value), precision(setPrecision().value), delimiter(setDelimiter().value) {} OutputDevice(OutputDevice const&) = delete; OutputDevice& operator = (OutputDevice const&) = delete;
virtual void writeToDevice(uint count) = 0;
inline void flushMaybe() { if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) { writeToDevice(BUFFER_SIZE); output = copy(buffer + BUFFER_SIZE, output, buffer); } }
template inline char* writeUnsignedInt(I arg, char* last) { if (__builtin_expect(arg == 0, false)) *--last = '0'; if (__builtin_expect(base == 10, true)) { for (; arg; arg /= 10) *--last = '0' + arg % 10; } else for (; arg; arg /= base) { I digit = arg % base; *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit; } return last; }
template inline char* writeSignedInt(I arg, char* last) { auto unsignedArg = static_cast::type>(arg); if (arg < 0) { last = writeUnsignedInt(~unsignedArg + 1, last); *--last = '-'; return last; } return writeUnsignedInt(unsignedArg, last); }
template char* writeFloatingPoint(F arg, char* last) { bool negative = signbit(arg); if (negative) arg = -arg; if (isnan(arg)) for (int i = 0; i < 3; ++i) *--last = i["NaN"]; else if (isinf(arg)) for (int i = 0; i < 3; ++i) *--last = i["fnI"]; else { auto integerPart = static_cast(arg); arg -= integerPart; for (int i = 0; i < precision; ++i) arg *= base; auto fractionalPart = static_cast(arg); if ((arg - fractionalPart) * 2 >= static_cast(1)) { if (precision == 0) ++integerPart; else ++fractionalPart; } if (precision > 0) { char* point = last - precision; last = writeUnsignedInt(fractionalPart, last); ::fill(point, last, '0'); last = point; *--last = '.'; } last = writeUnsignedInt(integerPart, last); } if (negative) *--last = '-'; return last; }
inline int writeT(char* first) { int delimiterLenght = separate ? writeDelimiter() : 0; separate = true; int charsWritten = static_cast(end - first); if (__builtin_expect(charsWritten < width, false)) charsWritten += writeFill(width - charsWritten); output = copy(first, end, output); flushMaybe(); return delimiterLenght + charsWritten; }
inline int writeFill(int count) { int result = count; if (__builtin_expect(output + count + MAX_LENGTH < end, true)) { if (count == 1) *output++ = fill; else output = fill_n(output, count, fill); } else for (uint chunkSize = static_cast(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) { if (chunkSize > count) chunkSize = count; output = fill_n(output, chunkSize, fill); flushMaybe(); if ((count -= chunkSize) == 0) break; } return result; }
public: int width; char fill; uint base; uint precision; string delimiter;
inline int writeChar(char arg) { separate = false; *output++ = arg; flushMaybe(); return 1; }
inline int writeString(const char* arg, int count, bool checkWidth = true) { separate = false; int result = count + (checkWidth && count < width ? writeFill(width - count) : 0); if (__builtin_expect(output + count + MAX_LENGTH < end, true)) { if (count == 1) *output++ = *arg; else output = copy_n(arg, count, output); } else for (int chunkSize = static_cast(buffer + BUFFER_SIZE - output);; chunkSize = BUFFER_SIZE) { if (chunkSize > count) chunkSize = count; output = copy_n(arg, chunkSize, output); flushMaybe(); if ((count -= chunkSize) == 0) break; arg += chunkSize; } return result; }
inline int writeDelimiter() { return writeString(delimiter.c_str(), static_cast(delimiter.size()), false); }
template inline int writeUnsignedInt(I arg) { return writeT(writeUnsignedInt(arg, end)); } template inline int writeSignedInt(I arg) { return writeT(writeSignedInt(arg, end)); } template inline int writeFloatingPoint(F arg) { return writeT(writeFloatingPoint(arg, end)); }
inline void flush() { writeToDevice(static_cast(output - buffer)); output = buffer; } virtual ~OutputDevice() {}; };
class OutputFile : public OutputDevice { FILE* file; bool owner;
void writeToDevice(uint count) override { fwrite(buffer, 1, count, file); fflush(file); }
public: OutputFile(FILE* file = stdout, bool takeOwnership = false) : file(file), owner(takeOwnership) {} OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {} ~OutputFile() override { flush(); if (owner) fclose(file); } };
class OutputString : public OutputDevice { string& str;
void writeToDevice(uint count) override { str.append(buffer, count); }
public: OutputString(string& str) : OutputDevice(), str(str) {} ~OutputString() override { flush(); } };
/************************************************ read & write ************************************************/ //unique_ptr input; unique_ptr input; //unique_ptr output; unique_ptr output;
// property setters inline int read(Detail::Base base) { input->base = base.value; return 0; } // primitive types inline int read() { return 0; } inline int read(char& arg) { return input->readChar(arg); } template inline typename enable_if::value && is_unsigned::value, int>::type read(I& arg) { return input->readUnsignedInt(arg); } template inline typename enable_if::value && is_signed::value, int>::type read(I& arg) { return input->readSignedInt(arg); } template inline typename enable_if::value, int>::type read(F& arg) { return input->readFloatingPoint(arg); } // characters skip inline int read(const char& arg) { input->skipCharacters([arg](char c) { return arg != c; }); return 0; } inline int read(const char* arg) { if (*arg) input->skipCharacters([arg](char c) { return InputDevice::isOneOf(c, arg); }); else input->skipCharacters(); input->putBack(); return 0; } inline int read(bool (isSkipped)(char)) { input->skipCharacters(isSkipped); input->putBack(); return 0; } // forward declarations so everything compiles template int read(char arg, int limit, bool (isTerminator)(char), Ts&&... args); template int read(char arg, int limit, const char* terminators, Ts&&... args); template ())> int read(Iterator first, Iterator last, Ts&&... args); template ())> int read(Iterator first, int count, Ts&&... args); template ::value, void>::type> int read(T&& arg1, Ts&&... args); // C strings inline int read(char* arg, int limit, const char* terminators = "") { if (!terminators) return input->readString(arg, limit, InputDevice::isSpace); else return input->readString(arg, limit, [terminators](char c) { return InputDevice::isOneOf(c, terminators); }); } template inline int read(char first, char* last, Ts&&... args) { return read(first, static_cast(last - first), forward(args)...); } template inline int read(char (&arg)[N], Ts&&... args) { return read(static_cast(arg), N, forward(args)...); } template inline int read(char* arg, int limit, bool (isTerminator)(char), Ts&&... args) { int argsRead = input->readString(arg, limit, isTerminator); return argsRead + read(forward(args)...); } template inline int read(char arg, int limit, const char* terminators, Ts&&... args) { int argsRead = read(arg, limit, terminators); return argsRead + read(forward(args)...); } // complex types and ranges template inline int read(pair& arg) { return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0; } template inline int read(vector& arg) { uint n; if (read(n) == 0) return 0; arg.resize(n); return read(arg.begin(), arg.end()); } template int read(Iterator first, Iterator last, Ts&&... args) { int success = 1; for (; first != last; ++first) success &= read(*first); return success + read(forward(args)...); } template int read(Iterator first, int count, Ts&&... args) { return read(first, first + count, forward(args)...); } template inline int read(T&& arg1, Ts&&... args) { int argsRead = read(forward(arg1)); return argsRead + read(forward(args)...); }
// property setters inline int write(Detail::Width width) { output->width = static_cast(width.value); return 0; } inline int write(Detail::Fill fill) { output->fill = fill.value; return 0; } inline int write(Detail::Base base) { output->base = base.value; return 0; } inline int write(Detail::Precision precision) { output->precision = precision.value; return 0; } inline int write(Detail::Delimiter delimiter) { output->delimiter = delimiter.value; return 0; } // primitive types inline int write() { return 0; } inline int write(char arg) { return output->writeChar(arg); } template inline typename enable_if::value && is_unsigned::value, int>::type write(I arg) { return output->writeUnsignedInt(arg); } template inline typename enable_if::value && is_signed::value, int>::type write(I arg) { return output->writeSignedInt(arg); } template inline typename enable_if::value, int>::type write(F arg) { return output->writeFloatingPoint(arg); } // complex types inline int write(const char* arg) { return output->writeString(arg, static_cast(strlen(arg))); } template inline int write(char (&arg)[N]) { return output->writeString(arg, static_cast(strlen(arg))); } inline int write(const string& arg) { return output->writeString(arg.c_str(), static_cast(arg.size())); } template inline int write(const pair& arg) { int charsWritten = write(arg.first); charsWritten += output->writeDelimiter(); return charsWritten + write(arg.second); } // forward declarations so everything compiles template ::value, decltype(*std::declval())>::type> int write(Iterator first, Iterator last, Ts&&... args); template ::value, decltype(*std::declval())>::type> int write(Iterator first, int count, Ts&&... args); template int write(T&& arg, T2&& arg2, Ts&&... args); // ranges template int write(Iterator first, Iterator last, Ts&&... args) { int charsWritten = 0; for (; first != last; charsWritten += ++first == last ? 0 : output->writeDelimiter()) charsWritten += write(*first); return charsWritten + write(forward(args)...); } template int write(Iterator first, int count, Ts&&... args) { return write(first, first + count, forward(args)...); } template inline int write(T&& arg, T2&& arg2, Ts&&... args) { int charsWritten = write(forward(arg)); return charsWritten + write(forward(arg2), forward(args)...); } template inline int writeln(Ts&&... args) { return write(forward(args)..., '\n'); }
void flush() { output->flush(); }
template class GraphUL { int n, m; vector adjacent[V];
public: GraphUL(int newn = 0, int newm = -1) : n(0) { init(newn, newm); }
void init(int newn, int newm = -1) { for (int i = 0; i < n; ++i) vector().swap(adjacent[i]); n = newn; m = newm >= 0 ? newm : n; }
void addEdge(int u, int v) { assert(u < n && v < m); adjacent[u].push_back(v); if (!ORIENTED && u != v) adjacent[v].push_back(u); }
bool oriented() const { return ORIENTED; } int size() const { return n; } int size2() const { return m; } const vector& operator [] (int v) const { return adjacent[v]; } };
template class SegmentTree { int n; vector tree;
public: SegmentTree(int newn = 0) { init(newn); } void init(int newn) { n = newn; vector(2*n).swap(tree); }
int size() const { return n; } T& operator [] (int i) { return tree[i + n]; } const T& operator [] (int i) const { return tree[i + n]; }
void build() { for (int i = n; --i; ) tree[i] = combine(tree[i<<1], tree[i<<1|1]); }
void set(int i, const T& value) { for (tree[i += n] = value; i >>= 1; ) tree[i] = combine(tree[i<<1], tree[i<<1|1]); }
void add(int i, const T& delta) { assert(COMMUTATIVE); for (i += n; i; i >>= 1) tree[i].add(delta); }
T query(int l, int r) const { // [l, r) T resl = T(), resr = T(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) if (COMMUTATIVE) { if (l&1) resl.add(tree[l++]); if (r&1) resr.add(tree[--r]); } else { if (l&1) resl = combine(resl, tree[l++]); if (r&1) resr = combine(tree[--r], resr); } return combine(resl, resr); } };
template struct Tmax { T value; Tmax(const T& value = -numeric_limits::max()) : value(value) {} inline operator T() const { return value; } inline void add(const Tmax& other) { smax(value, other.value); } friend inline Tmax combine(const Tmax& lhs, const Tmax& rhs) { return max(lhs.value, rhs.value); } }; namespace std { template struct numeric_limits> { constexpr static T max() { return numeric_limits::max(); } }; }
template class LCA { public: int i, treePos; int root[V], depth[V+1], pos[V];
struct Imin { static int* data; int index; Imin(int index = V) : index(index) {} operator int() const { return index; } void add(const Imin& other) { if (data[other] < data[index]) index = other; } friend Imin combine(const Imin& lhs, const Imin& rhs) { return data[rhs] < data[lhs] ? rhs : lhs; } }; SegmentTree tree;
template void dfs(const G& graph, int v) { root[v] = i; pos[v] = treePos; tree[treePos++] = v; for (int u : graph[v]) if (pos[u] == -1) { depth[u] = depth[v] + 1; dfs(graph, u); tree[treePos++] = v; } }
template void build(const G& graph) { depth[V] = V; int n = graph.size(); treePos = 0; fill_n(pos, n, -1); tree.init(2 * n - 1); for (i = 0; i < n; ++i) if (pos[i] == -1) { depth[i] = 0; dfs(graph, i); } Imin::data = depth; tree.build(); }
int lca(int u, int v) { if (root[u] != root[v]) return -1; if (pos[u] > pos[v]) swap(u, v); Imin::data = depth; return tree.query(pos[u], pos[v] + 1).index; } }; template int* LCA::Imin::data;
const int N = 75e3+3; int n, m; GraphUL graph; LCA lca;
pii p[N], l[N]; int sum[N]; int o[N];
int main() {
ifdef LocalHost
input.reset(new InputFile("input.txt")); //input.reset(new InputFile()); output.reset(new OutputFile()); //output.reset(new OutputFile("output2.txt"));
else
input.reset(new InputFile(stdin, false)); //input.reset(new InputFile()); output.reset(new OutputFile());
endif
read(n, m); graph.init(n); REP(i, n-1) { int u, v; read(u, v); --u; --v; graph.addEdge(u, v); } lca.build(graph);
read(p, m); int h = 0; REP(i, m) { --p[i].X; --p[i].Y; sum[i] = lca.depth[p[i].X] + lca.depth[p[i].Y]; if (sum[i] > sum[h]) h = i; }
REP(i, m) { l[i].X = lca.depth[lca.lca(p[i].X, p[h].X)]; l[i].Y = lca.depth[lca.lca(p[i].Y, p[h].Y)]; o[i] = i; } sort(o, o + m, [](int i, int j) { return l[i].X > l[j].X || (l[i].X == l[j].X && l[i].Y < l[j].Y); });
SegmentTree> tree(l[h].Y+1); int ans = 0; REP(i, m) { int j = o[i]; int t = tree.query(0, l[j].Y+1); if (t >= -2*n) smax(ans, sum[j] - 2 * l[j].X + t); if (i > 0) smax(ans, sum[h] + sum[j] - 2 * (l[j].X + l[j].Y)); tree.add(l[j].Y, sum[j] - 2 * l[j].Y); } writeln(ans);
ifdef LocalHost
flush(); cerr << endl << endl << static_cast(clock()) / CLOCKS_PER_SEC << endl;
endif
return 0; }