#6 有个搬题人搬的题很好但题搬得很差
Infinite Game
题面
感觉是一个比较经典的自动机dp。对于一个回合，有效的只有 \(0:0,0:1,1:0,1:1\) 这 \(4\) 种情况。将这种情况分别看作 \(1,2,3,4\)。可以发现最后一定能形成环，因为我们如果我们把字符串看成一轮，用一轮开始环上的点的状态表示这一轮的环，那么在无限轮之后一定有重复的，即一定存在环。
如果我们简单从 \(0\) 开始走，走完一遍后重新走，这是不对的，因为我们需要保证中间过程中的 ? 每一轮选到字母是一样的。于是我们想到可以将四个状态都记录下来，令 \(f_{i,a,b,c,d}\) 表示走 \(i\) 步，且起点为 \(0,1,2,3\) 时走到 \(a,b,c,d\) 的方案数。
统计答案直接统计两人的胜场之差，但这只在最后的环上会产生贡献。我们考虑枚举最后环上会出现的点的点集，只统计最后构成的环上的点和枚举的点集相同的情况产生的贡献。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=410,mx=400,mod=998244353;
int n,f[N<<1][4][4][4][4],g[N<<1][4][4][4][4],nxt[4][2],ans[4];
char s[N];
void solve(){
nxt[0][0]=1,nxt[0][1]=2;
nxt[1][0]=0,nxt[1][1]=3;
nxt[2][0]=3,nxt[2][1]=0;
nxt[3][0]=nxt[3][1]=0;
cin>>(s+1);
n=strlen(s+1);
for(int S=0;S<16;S++){
memset(f,0,sizeof(f));
f[mx][0][1][2][3]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=mx*2;j++){
for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++)for(int d=0;d<4;d++){
if(!f[j][a][b][c][d]){
continue;
}
for(int k=0;k<2;k++){
if(s[i]-'a'!=k&&s[i]!='?'){
continue;
}
int nxta=nxt[a][k],nxtb=nxt[b][k],nxtc=nxt[c][k],nxtd=nxt[d][k];
int nxtj=((S&1)&&(a&(k+1)))+((S&2)&&(b&(k+1)))+((S&4)&&(c&(k+1)))+((S&8)&&(d&(k+1)));
nxtj=(k?j+nxtj:j-nxtj);
g[nxtj][nxta][nxtb][nxtc][nxtd]=(g[nxtj][nxta][nxtb][nxtc][nxtd]+f[j][a][b][c][d])%mod;
}
}
}
for(int j=0;j<=mx*2;j++){
for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++)for(int d=0;d<4;d++){
f[j][a][b][c][d]=g[j][a][b][c][d];
g[j][a][b][c][d]=0;
}
}
}
for(int a=0;a<4;a++)for(int b=0;b<4;b++)for(int c=0;c<4;c++)for(int d=0;d<4;d++){
int trans[4]={a,b,c,d},x=0;
for(int i=0;i<10;i++){
x=trans[x];
}//保证能走到环上就行
int st=0;
for(int i=0;i<10;i++){
st|=(1<<x);
x=trans[x];
}//判断点集与环上的点是否相同。
if(st!=S){
continue;
}
for(int j=0;j<=mx*2;j++){
ans[(j>=mx)+(j>mx)]=(ans[(j>=mx)+(j>mx)]+f[j][a][b][c][d])%mod;
}
}
}
write_endl(ans[0]);
write_endl(ans[1]);
write_endl(ans[2]);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[USACO23FEB] Watching Cowflix P
题面
先做 \(O(n^2)\) 的做法吧，令 \(f_{i,0/1}\) 表示点 \(i\) 选或不选的最小代价，转移比较简单，把所有的基础贡献在连通块中度数再去加。\(f_{u,0}=\min(f_{v,0},f_{v,1}+k),f_{u,1}=1+\min(f_{v,0},f_{v,1})\)。最后特殊处理下根就可以了。
可以发现有个链的部分分，我们考虑对于一个序列，我们该怎么做。有一个显然正确的贪心策略，如果两个点之间的距离小于 \(k\)，我们必然把这两个放在一个连通块中，因为从一个连通块扩展到另一个连通块的代价小于建一个新连通块，更优。这个策略同样可以放到树上，我们可以得到，树上的连通块的数量不会超过 \(\frac{n+k}{k+1}\)，可以近似看作 \(\frac{n}{k}\)，我们将连通块建出虚树，在虚树上跑上述的dp，复杂度 \(O(\sum\limits_{k=1}^n{\frac{n}{k}})=O(n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,inf=1e9;
int n,f[N][2],fa[N],idx,k,pos[N],dep[N],val[N],rpos[N],all;
char s[N];
vector<int>e[N],G[N];
int make_tree(int u,int father){
dep[u]=dep[father]+1;
int cnt=0,Pos=0;
for(auto v:e[u]){
if(v==father){
continue;
}
int p=make_tree(v,u);
if(!p){
continue;
}
if(Pos){
fa[Pos]=u;
}
Pos=p;
cnt++;
}
if(cnt<=1&&s[u]=='0'){
return Pos;
}
else{
pos[++idx]=u;
fa[Pos]=u;
return u;
}
}
void dfs(int u){
f[u][0]=(s[u]=='1'?inf:0);
f[u][1]=1;
for(auto v:G[u]){
dfs(v);
f[u][0]+=min(f[v][0],f[v][1]+k);
f[u][1]+=min(f[v][0],f[v][1]+min(k,val[v]));
}
}
void merge(int u,int opt){
if(opt){
s[u]='1';
}
for(auto v:G[u]){
fa[v]=rpos[u];
if(!opt){
merge(v,f[v][1]+k<=f[v][0]);
continue;
}
int type=(f[v][1]+min(k,val[v])<=f[v][0]);
if(type&&val[v]<=k){
rpos[v]=rpos[u];
all+=val[v]+1;
}
merge(v,type);
}
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
s[i]=getchar();
while(s[i]!='0'&&s[i]!='1'){
s[i]=getchar();
}
}
for(int i=1;i<n;i++){
int u,v;
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
int rt=make_tree(1,0);
for(int i=1;i<=idx;i++){
val[pos[i]]=dep[pos[i]]-dep[fa[pos[i]]]-1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=idx;j++){
if(fa[pos[j]]){
G[fa[pos[j]]].pb(pos[j]);
}
}
for(int j=1;j<=idx;j++){
rpos[pos[j]]=pos[j];
}
k=i;
dfs(rt);
write_endl(min(f[rt][0],f[rt][1]+i)+all);
int id=0;
merge(rt,f[rt][1]+i<=f[rt][0]);
for(int j=1;j<=idx;j++){
G[pos[j]].clear();
G[pos[j]].shrink_to_fit();
}
for(int j=1;j<=idx;j++){
if(rpos[pos[j]]==pos[j]){
pos[++id]=pos[j];
}
}
idx=id;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
马超战潼关
题面
可以发现原图就是一个网络流求二分图最大匹配的模型，最小割大小一定为最大匹配的大小。
求出一个最大匹配方案。构造一张图，每个点代表一个匹配，用点权 \(0,1,2\) 表示匹配 \((u,v)\) 所在路径选择割 \((S,u),(u,v),(v,T)\) 三条边。设 \(val_i\) 表示第 \(i\) 条匹配边的点权。对于一条边 \((e_u,e_v)\)，设 \(x\) 为 \(e_u\) 所在匹配，\(y\) 为 \(e_v\) 所在匹配，\(e_u,e_v\) 若不在匹配中，则 \(x,y\) 为 \(0\)。
对于一条不在匹配中的边 \((e_u,e_v)\)，因为匹配的最大性，所以 \(e_u,e_v\) 必有至少一个在匹配中。
- 若 \(x>0,y=0\)，则 \(val_x=0\)。
- 若 \(x=0,y>0\)，则 \(val_y=2\)。
- 若 \(x>0,y>0\)，则 \(val_x=0\text{或}val_y=2\)
对于最后一种情况，我们从 \(x\) 向 \(y\) 连一条边。根据情况 \(3\) 的限制，可以发现在新图中如果存在一条边 \((u,v)\)，\(val_u\le val_v\text{且不存在}val_u=val_v=1\)。即对于图上一条链，点权一定类似于 \(0\rightarrow 0\rightarrow 0\rightarrow (1)\rightarrow 2\rightarrow 2\rightarrow 2\) 的样子，其中点权为 \(1\) 的点可以不必出现。
将新得到的这张图进行一个缩点操作，显然环中所有点点权应相同，且没有点点权为 \(1\)。缩点后可以得到一个DAG，求出拓扑序。因为数据较大，考虑 meet in the middle,枚举前一半点的权值，可以限制后一半某些点必须选 \(2\)，预处理后一半的情况，做一遍高维前缀和，可以得到 \(O(3^n n^2)\) 的算法，这是不够的。
但我们新图中还有一个极为重要的性质是没有用上的——\(1\) 至多出现一个。所以可以前半部分只限制是否选 \(0\)，后半部分能为 \(1\) 的只有导出子图中入度为 \(0\) 的点，反过来，限制后半部分做一遍对称的，只限制是否选 \(2\)，前半部分能为 \(1\) 的只有导出子图中出度为 \(0\) 的点。预处理前半部分，做高位前缀和即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll __int128_t
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=510,M=9e6+10;
int n,m;
ll ans;
struct edge{
int u,v;
}e[N];
int id1[N],id2[N],idx,reach_small[N],reach_large[N];
int f[M];
namespace KM{
int must_be_0[N],must_be_2[N],vis[N],couple[N],cnt;
vector<int>G[N];
int find(int u,int tag){
if(vis[u]==tag){
return 0;
}
vis[u]=tag;
for(auto i:G[u]){
int v=e[i].v;
if(!couple[v] || find(e[couple[v]].u,tag)){
couple[v]=i;
return 1;
}
}
return 0;
}
}
namespace Tarjan{
vector<int>G[N];
int dfn[N],low[N],stk[N],top,cnt=0,in_stack[N];
int must_be_0[N],must_be_2[N],cant_be_1[N],col[N],col_cnt;
void dfs(int u){
dfn[u]=low[u]=++cnt;
in_stack[u]=1;
stk[++top]=u;
for(auto v:G[u]){
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(in_stack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
int sum=0;
while(1){
int v=stk[top--];
sum++;
must_be_0[col_cnt]|=KM::must_be_0[v];
must_be_2[col_cnt]|=KM::must_be_2[v];
in_stack[v]=0;
col[v]=col_cnt;
if(v==u){
break;
}
}
if(sum>1){
cant_be_1[col_cnt]=1;
}
++col_cnt;
}
}
}
namespace DAG{
int in[N],out[N],vis[N];
vector<int>G[N];
void dfs(int u){
if(vis[u]){
return;
}
vis[u]=1;
for(auto v:G[u]){
dfs(v);
}
}
void solve(){
int cnt=Tarjan::col_cnt,l=cnt/2,r=cnt-l;
for(int i=0;i<cnt;i++){
for(int j=0;j<cnt;j++){
vis[j]=0;
}
dfs(i);
for(int j=0;j<l;j++){
if(vis[j]){
reach_small[i]|=(1ll<<j);
}
}
for(int j=l;j<cnt;j++){
if(vis[j]){
reach_large[i]|=(1ll<<j);
}
}
}
for(int S=0;S<(1ll<<l);S++){
int R=((1ll<<l)-1)^S,flag=1;
for(int i=0;i<l&&flag;i++){
if(S>>i&1ll){
if(Tarjan::must_be_0[i]){
flag=0;
}
if((reach_small[i]&S)!=reach_small[i]){
flag=0;
}
}
else if(Tarjan::must_be_2[i]){
flag=0;
}
}
if(!flag){
continue;
}
int tot=0;
for(int i=0;i<l;i++){
if(S>>i&1ll){
continue;
}
if(((out[i]&R)==0ll)&&(!Tarjan::must_be_0[i])&&(!Tarjan::must_be_2[i])&&(!Tarjan::cant_be_1[i])){
tot++;
}
}
f[S]=(1ll<<tot);
}
for(int k=1;k<(1ll<<l);k*=2){
for(int i=0;i<(1ll<<l);i+=k*2){
for(int j=i;j<i+k;j++){
f[j]+=f[j+k];
}
}
}
for(int T=0;T<(1ll<<r);T++){
int S=T<<l,flag=1;
for(int i=l;i<l+r&&flag;i++){
if(S>>i&1ll){
if(Tarjan::must_be_0[i]){
flag=0;
}
if((reach_large[i]&S)!=reach_large[i]){
flag=0;
}
}
else if(Tarjan::must_be_2[i]){
flag=0;
}
}
if(!flag){
continue;
}
int R=0,tot=0;
for(int i=l;i<l+r;i++){
if(!(S>>i&1ll)){
continue;
}
R|=reach_small[i];
if(((in[i]&S)==0ll)&&(!Tarjan::must_be_0[i])&&(!Tarjan::must_be_2[i])&&(!Tarjan::cant_be_1[i])){
tot++;
}
}
ans+=(1ll<<tot)*f[R];
}
write_endl(ans);
}
}
void solve(){
read(n),read(m);
for(int i=1;i<=m;i++){
read(e[i].u),read(e[i].v);
KM::G[e[i].u].pb(i);
}
for(int i=1;i<=n;i++){
KM::cnt+=KM::find(i,i);
}
for(int i=1;i<=n;i++){
if(KM::couple[i]){
id1[e[KM::couple[i]].u]=id2[i]=++idx;
}
}
for(int i=1;i<=m;i++){
if(i==KM::couple[e[i].v]){
continue;
}
int u=id1[e[i].u],v=id2[e[i].v];
if(u&&!v){
KM::must_be_0[u]=1;
}
else if(!u&&v){
KM::must_be_2[v]=1;
}
else if(u&&v){
Tarjan::G[u].pb(v);
}
}
for(int i=1;i<=KM::cnt;i++){
if(!Tarjan::dfn[i]){
Tarjan::dfs(i);
}
}
for(int u=1;u<=KM::cnt;u++){
for(auto v:Tarjan::G[u]){
int x=Tarjan::col[u],y=Tarjan::col[v];
if(x!=y){
DAG::G[x].pb(y);
DAG::in[y]|=(1ll<<x);
DAG::out[x]|=(1ll<<y);
}
else{
Tarjan::cant_be_1[x]=1;
}
}
}
DAG::solve();
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}
The Child and Sequence
题面
注意到取模的性质：
令 \(a\equiv r\pmod x\)，得 \(a=kx+r(r<x)\)。
若 \(k>0\)，则 \(a>2r\)，若 \(k=0\)，则 \(a=r\)。
一次取模过后，如果一个值变小了，那么它至少会减小到一半，因此一个数 \(a\) 最多进行 \(\log a\) 次有效取模。
可以使用线段树维护和，操作一和操作三是最经典的线段树单点修改，区间查询。对于操作二，因为取模操作不能区间操作然后 pushdown，显然我们只能暴力修改。容易得到的是不需要对所有的区间进行操作，可能被修改的区间只有最大值大于等于 \(x\) 的数才会被修改。因此我们在维护区间和时同时维护区间最大值，修改时如果当前区间最大值小于 \(x\) 直接返回。复杂度 \(O(q\log n\log V)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,m,a[N];
namespace Seg_Tree{
int ans[N<<2],mx[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p){
ans[p]=ans[ls(p)]+ans[rs(p)];
mx[p]=max(mx[ls(p)],mx[rs(p)]);
}
void build(int p,int l,int r){
if(l==r){
ans[p]=mx[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void update(int p,int l,int r,int q_l,int q_r,int mod){
if(mx[p]<mod){
return;
}
if(l==r){
ans[p]%=mod;
mx[p]%=mod;
return;
}
int mid=(l+r)>>1;
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r,mod);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r,mod);
}
push_up(p);
}
void change(int p,int l,int r,int pos,int val){
if(l==r){
ans[p]=mx[p]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
change(ls(p),l,mid,pos,val);
}
else{
change(rs(p),mid+1,r,pos,val);
}
push_up(p);
}
int query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return ans[p];
}
int mid=(l+r)>>1,res=0;
if(q_l<=mid){
res+=query(ls(p),l,mid,q_l,q_r);
}
if(q_r>mid){
res+=query(rs(p),mid+1,r,q_l,q_r);
}
return res;
}
}
void solve(){
read(n),read(m);
for(int i=1;i<=n;i++){
read(a[i]);
}
Seg_Tree::build(1,1,n);
for(int i=1;i<=m;i++){
int opt,l,r,val;
read(opt);
if(opt==1){
read(l),read(r);
write_endl(Seg_Tree::query(1,1,n,l,r));
}
else if(opt==2){
read(l),read(r),read(val);
Seg_Tree::update(1,1,n,l,r,val);
}
else{
read(l),read(val);
Seg_Tree::change(1,1,n,l,val);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Freezing with Style
题面
中位数不好处理，考虑二分中位数 \(x\)，将大于等于 \(x\) 的数记为 \(+1\)，将小于 \(x\) 的数记为 \(-1\)，这样只要判断树上是否有一条满足条件且权值和大于等于 \(0\) 的路径即可。
对于路径问题容易想到点分治，用贪心的思想做，对于深度相同的链，我们只保存边权和最大的。令 \(f_i\) 表示之前所有处理过的子树中深度为 \(i\) 的链的边权和最大值，\(g_i\) 表示当前正在处理的子树中深度为 \(i\) 的链的边权和最大值。要求的就是 \(\max\{f_i+g_j|l\le i+j\le r\}\ge 0\)。容易发现这个是像滑动窗口的操作，可以用单调队列维护。但我们注意到如果直接做，单调队列的大小是 \(O(n)\) 的。令 \(pre\) 表示处理过的子树中的点的最大深度，\(now\) 表示当前子树中的点的最大深度，当 \(pre\le now\) 时，单调队列的大小为 \(O(pre)\)。
于是我们得到了在 calc 时先将子树按照最大深度大小排序的做法，这样的复杂度为 \(O(\sum pre)=O(n)\)，对于排序，因为每个子树对应一条子树根到分治中心的边，所以排序总复杂度为 \(O(n\log n)\)
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,inf=1e9;
int n,l,r,ansu,ansv,head[N],tot=1;
struct edge{
int v,w,nxt;
}e[N<<1];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void add_e(int u,int v,int w){
add(u,v,w);
add(v,u,w);
}
int vis[N],siz[N],dep[N],mx[N],rt;
void get_rt(int u,int fa,int sz){
siz[u]=1;
mx[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa||vis[v]){
continue;
}
get_rt(v,u,sz);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u],sz-siz[u]);
if(mx[rt]>mx[u]){
rt=u;
}
}
int maxdep[N],weight[N],f[N],f_pos[N],g[N],g_pos[N],dis[N];
void dfs(int st,int u,int fa,int Dep,int Len,int val,int rt){
dep[u]=Dep;
maxdep[st]=max(maxdep[st],dep[u]);
dis[u]=Len;
if(dis[u]>g[dep[u]]){
g[dep[u]]=dis[u];
g_pos[dep[u]]=u;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(v==fa||vis[v]){
continue;
}
dfs(st,v,u,Dep+1,Len+(w>=val?1:-1),val,rt);
}
}
int num[N],que[N];
bool cmp(int x,int y){
return maxdep[x]<maxdep[y];
}
int calc(int u,int val){
int tot=0,Maxdep=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(vis[v]){
continue;
}
num[++tot]=v;
maxdep[v]=0;
weight[v]=w;
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(vis[v]){
continue;
}
dfs(v,v,u,1,w>=val?1:-1,val,u);
Maxdep=max(Maxdep,maxdep[v]);
}
sort(num+1,num+tot+1,cmp);
for(int i=0;i<=Maxdep;i++){
g[i]=f[i]=-inf;
f_pos[i]=g_pos[i]=0;
}
f[0]=0;
f_pos[0]=u;
for(int i=1;i<=tot;i++){
int v=num[i],w=weight[v];
if(vis[v]){
continue;
}
dfs(v,v,u,1,w>=val?1:-1,val,u);
int now=0,head,tail;
head=tail=1;
for(int j=min(r,maxdep[v]);j>=0;j--){
while(now<=maxdep[num[i-1]]&&now+j<=r){
while(head<tail&&f[que[tail-1]]<f[now]){
tail--;
}
que[tail++]=now;
now++;
}
while(head<tail&&que[head]+j<l){
head++;
}
if(head<tail&&que[head]+j<=r&&f[que[head]]+g[j]>=0){
ansu=f_pos[que[head]],ansv=g_pos[j];
return 1;
}
}
for(int j=0;j<=maxdep[v];j++){
if(g[j]>f[j]){
f[j]=g[j];
f_pos[j]=g_pos[j];
}
g[j]=-inf;
g_pos[j]=0;
}
}
return 0;
}
int divide(int u,int sz,int val){
if(calc(u,val)){
return 1;
}
rt=0;
get_rt(u,0,sz);
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]){
continue;
}
int Siz=siz[v];
rt=0;
get_rt(v,u,Siz);
if(divide(rt,Siz,val)){
return 1;
}
}
return 0;
}
bool check(int x){
for(int i=1;i<=n;i++){
vis[i]=0;
}
ansu=ansv=0;
mx[0]=inf;
rt=0;
get_rt(1,0,n);
return divide(rt,n,x);
}
void solve(){
int L=inf,R=0;
read(n),read(l),read(r);
for(int i=1,u,v,w;i<n;i++){
read(u),read(v),read(w);
add_e(u,v,w);
L=min(L,w);
R=max(R,w);
}
int ans=L;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid)){
L=mid+1;
ans=mid;
}
else{
R=mid-1;
}
}
check(ans);
write_space(ansu),write_endl(ansv);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}