写的 3 log,有大佬过了,本菜鸡一直 TLE on #22,求卡常。
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
}
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define ls id << 1
#define rs id << 1 | 1
#define int long long
#define re register
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
int n,L,R,head[MAXN],b[MAXN],cnt,x,y,z,ans,maxn = 0;
int pt,ansx,ansy,mi;
bool vis[MAXN],flag = false;
struct F{int u,num,dis;}p[MAXN];
struct Node{int u,v,w,nxt;}e[MAXN <<1],g[MAXN << 1];
struct SegmentTree{int l,r,mx,node;}tree[MAXN << 2];
inline void Add(int u,int v,int w){e[++cnt] = {u,v,w,head[u]};head[u] = cnt;}
inline int Get_size(int u,int father)
{
if(vis[u] == true) return 0;
re int sum = 1;
for(re int i = head[u]; ~ i;i = e[i].nxt)
if(e[i].v != father) sum += Get_size(e[i].v,u);
return sum;
}
inline int Get_wc(int u,int father,int tot,int &wc)
{
if(vis[u] == true) return 0;
re int sum = 1,mx = 0;
for(re int i = head[u]; ~ i;i = e[i].nxt)
{
re int now = e[i].v;
if(now == father) continue;
re int tmp = Get_wc(now,u,tot,wc);
sum += tmp,mx = max(mx,tmp);
}
if(max(mx,tot - sum) <= tot / 2) wc = u;
return sum;
}
inline void Get_dist(int u,int father,int num,int dis)
{
if(vis[u] == true) return;
p[++pt] = {u,num,dis};
for(re int i = head[u]; ~ i;i = e[i].nxt)
{
re int now = e[i].v;
if(now == father) continue;
Get_dist(now,u,num + 1,dis + (e[i].w >= mi ? 1 : -1));
}
}
inline void Pushup(int id)
{
if(tree[ls].mx > tree[rs].mx) tree[id].node = tree[ls].node;
else tree[id].node = tree[rs].node;
tree[id].mx = max(tree[ls].mx,tree[rs].mx);
}
inline void Build(int id,int l,int r)
{
tree[id].l = l,tree[id].r = r,tree[id].mx = -1e9;
tree[id].node = 0;
if(l == r) return;
re int mid = (l + r) >> 1;
Build(ls,l,mid),Build(rs,mid + 1,r);
}
inline void Update(int id,int l,int r,int a,int b,int c)
{
if(l == r)
{
if(b > tree[id].mx) tree[id].node = c;
tree[id].mx = max(tree[id].mx,b);return;
}
re int mid = (l + r) >> 1;
if(a <= mid) Update(ls,l,mid,a,b,c);
else Update(rs,mid + 1,r,a,b,c);
Pushup(id);
}
inline SegmentTree Query(int id,int l,int r,int a,int b)
{
if(a <= l && b >= r) return tree[id];
re int mid = (l + r) >> 1;
if(a > mid) return Query(rs,mid + 1,r,a,b);
if(b <= mid) return Query(ls,l,mid,a,b);
SegmentTree FL = Query(ls,l,mid,a,b),FR = Query(rs,mid + 1,r,a,b),res;
if(FL.mx > FR.mx) res.node = FL.node;
else res.node = FR.node;
res.mx = max(FL.mx,FR.mx);
return res;
}
inline void calc(int u)
{
if(vis[u] == true) return;
Get_wc(u,0,Get_size(u,0),u);
re int m = Get_size(u,0);vis[u] = true;
Build(1,1,m);
for(re int i = head[u]; ~ i;i = e[i].nxt)
{
re int now = e[i].v;
pt = 0;
Get_dist(now,u,1,e[i].w >= mi ? 1 : -1);
for(re int j = 1;j <= pt;j = -~j)
{
re int num = p[j].num,dis = p[j].dis,node = p[j].u;
if(num > R) continue;
if(num >= L && dis >= 0){ansx = u,ansy = node;flag = true;return;}
if(num == R) continue;
int f = max(1ll,L - num),s = min(m,R - num);
if(f > s)continue;
SegmentTree tmp = Query(1,1,m,f,s);
if(tmp.mx + dis >= 0 && tmp.node != 0){ansx = tmp.node,ansy = node;flag = true;return;}
}
for(re int j = 1;j <= pt;j = -~j)
{
re int num = p[j].num,dis = p[j].dis,node = p[j].u;
Update(1,1,m,num,dis,node);
}
}
for(re int i = head[u]; ~ i;i = e[i].nxt) calc(e[i].v);
}
inline bool check()
{
for(re int i = 1;i <= n;i = -~i) vis[i] = false;
flag = false,calc(1);
if(flag == true) return true;
else return false;
}
signed main()
{
memset(head,-1,sizeof head);
cin >> n >> L >> R;
for(re int i = 1;i < n;i = -~i) cin >> x >> y >> z,Add(x,y,z),Add(y,x,z),b[i] = z;
sort(b + 1,b + n);
re int len = unique(b + 1,b + n) - b - 1;
re int l = 1,r = len;
while(l <= r)
{
re int mid = (l + r) >> 1;
mi = b[mid];
if(check()) l = mid + 1,ans = b[mid];
else r = mid - 1;
}
cout << ansx << " " << ansy;
return 0;
}