danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29164

[CF 711D]Directed Roads

2016年8月30日 12:25 | Comments(0) | Category:题解 | Tags:

这个题啊……其实不难。

首先你注意,他告诉你你可以把边弄反。

其次注意,这个图不一定就有一个环。

然后每个环的取反法有[tex]2^x[/tex]种(假设环中有[tex]x[/tex]条边),但是空集不行,全集也不行,因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄,乘法原理乱搞即可。

然后你是不是感觉这个题似曾相识?是的似乎这个题就是NOIP D1T2的翻版。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200001;
const ll MOD=1000000007;
int G[maxn];
int in[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !in[i]){
            ans=true;
            in[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
ll dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
ll pow_mod(ll a,ll b){
    if(!b){
        return 1;
    }else{
        ll ans=pow_mod(a,b/2);
        ans=ans*ans%MOD;
        if(1&b){
            ans=(ans*(a%MOD))%MOD;
        }
        return ans;
    }
}
inline ll solve(){
	register int i;
	register ll Huan,temp=0,ans=1;
	while(jianz());
	for(i=1;i<=n;i++)
		if(!vis[i]){
			Huan=dfs(i,i);
			temp+=Huan;
			ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD;
		}
	ans=(ans*pow_mod(2,n-temp))%MOD;
	return ans;
}
int main(){
	register int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&G[i]);
		in[G[i]]++;
	}
	printf("%I64d\n",solve());
	return 0;
}

[BZOJ 1013]球型空间产生器

2016年8月29日 16:04 | Comments(0) | Category:题解 | Tags:

不行不能颓了……线代其实刚起步……

注意每个点到球心的距离相同,距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex],那么我们先可以列出两个方程(假设[tex]n=2[/tex],不过此时事实上可以列三个,但出于方便讨论的目的便只列两个):

[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]

[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]

两方程作差,得:

[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]

整理,得:

[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]

对这种方法加以推广,便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。

代码:

/**************************************************************
    Problem: 1013
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1296 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
    register int i,j,k,r;
    register double f;
    for(i=1;i<=n;i++){
        r=i;
        for(j=i+1;j<=n;j++)
            if(fabs(A[j][i])>fabs(A[r][i]))
                r=j;
        if(r!=i)
            for(j=1;j<=(n+1);j++)
                swap(A[r][j],A[i][j]);
        for(k=i+1;k<=n;k++){
            f=A[k][i]/A[i][i];
            for(j=i;j<=n+1;j++)
                A[k][j]-=f*A[i][j];
        }
    }
    for(i=n;i>=1;i--){
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[j][n+1]*A[i][j];
        A[i][n+1]/=A[i][i];
    }
}
int main(){
    register int i,j;
    bool flag=false;
    cin>>n;
    for(i=1;i<=(n+1);i++)
        for(j=1;j<=n;j++)
            cin>>M[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=(n+1);j++)
            A[i][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            A[i][j]=2*(M[i+1][j]-M[i][j]);
            A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
        }
    }
    Gause();
    for(i=1;i<=n;i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%.3f",A[i][n+1]);
    }
    putchar('\n');
    return 0;
}

[POJ 3461]Oulipo

2016年8月28日 21:42 | Comments(0) | Category:题解 | Tags:

字符串搜索提……同时是KMP模板提……

注意啊变量别重名,结果会很壮观的(大吐核)。

代码:

#include <cstdio>
#include <cstring>
const int maxn=1000005,maxm=10005;
char P[maxm],T[maxn];
int f[maxm];
int n,m;
inline void MakeFail(){
    register int i,j;
    f[0]=f[1]=0;
    for(i=1;i<m;i++){
        j=f[i];
        while(j && P[j]!=P[i])
            j=f[j];
        f[i+1]=(P[j]==P[i]?j+1:0);
    }
}
inline int KMP(){
    register int i,j,ans=0;
    n=strlen(T);
    m=strlen(P);
    MakeFail();
    j=0;
    for(i=0;i<n;i++){
        while(j && P[j]!=T[i])
            j=f[j];
        if(P[j]==T[i])
            j++;
        if(j==m)
            ans++;
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",P,T);
        printf("%d\n",KMP());
    }
    return 0;
}

[BZOJ 1477]青蛙的约会

2016年8月28日 19:59 | Comments(0) | Category:题解 | Tags:

设用时为[tex]t[/tex],则本题可视为解方程[tex](mt+x)-(nt+y)=kL[/tex]。

整理变形得[tex](n-m)t+Lk=x-y[/tex]。

明显需要扩欧求解。注意此题有很多细节,可参见下代码:

/**************************************************************
    Problem: 1477
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1288 kb
****************************************************************/
 
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b)
        return a;
    else
        return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,x,y);
        ll t=x;
        x=y;
        y=t-a/b*y;
    }
}
int main(){
    ll a,b,c,t,M,k;
    ll x,y,m,n,L;
    cin>>x>>y>>m>>n>>L;
    a=n-m;
    b=L;
    c=x-y;
    k=gcd(a,b);
    if(c%k!=0){
        cout<<"Impossible"<<endl;
        return 0;
    }
    a/=k;
    b/=k;
    c/=k;
    exgcd(a,b,k,t,M);
    t=(((c*t)%b)+b)%b;
    if(!t)
        t+=b;
    cout<<t<<endl;
    return 0;
}

[POJ 1274]The Perfect Stall

2016年8月28日 17:33 | Comments(0) | Category:题解 | Tags:

很裸的二分图匹配辣~

不过这是我第一次写匈牙利算法……囧

还有时隔多年再次写了一次邻接矩阵QwQ

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=201,maxm=40001;
bool G[maxn][maxn];

// Hungray
int n,m;
bool vis[maxn];
int GirlFriend[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int main(){
    register int i,j;
    int k,temp;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(G,0,sizeof(G));
        memset(GirlFriend,0,sizeof(GirlFriend));
        for(i=1;i<=n;i++){
            scanf("%d",&k);
            for(j=1;j<=k;j++){
                scanf("%d",&temp);
                G[i][temp]=true;
            }
        }
        printf("%d\n",Hungray());
    }
    return 0;
}

[BZOJ 3224]普通平衡树

2016年8月28日 12:50 | Comments(0) | Category:题解 | Tags:

很好,这很interesting。

最大坑点是数可能重复。然后前驱后驱赶脚也挺坑的……

还有好像BZOJ不滋磁time(0)哎。所以我就用了wyy的生日做随机数种子辣!

代码:

/**************************************************************
    Problem: 3224
    User: danihao123
    Language: C++
    Result: Accepted
    Time:376 ms
    Memory:1880 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Node{
    Node *ch[2];
    int v;
    int r;
    int s;
    int cnt;
    Node(){
        v=s=cnt=0;
        r=-1;
        ch[0]=ch[1]=NULL;
    }
    Node(int key,Node *lc,Node *rc){
        v=key;
        r=rand();
        s=1;
        cnt=1;
        ch[0]=lc;
        ch[1]=rc;
    }
    void maintain(){
        s=ch[0]->s+ch[1]->s+cnt;
    }
};
struct Treap{
    Node *null,*root;
    Treap(){
        null=new Node();
        root=null;
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }
    void insert(Node* &o,int x){
        if(o==null){
            o=new Node(x,null,null);
        }else{
            if(o->v==x){
                o->cnt++;
                o->s++;
            }else{
                int d=x>(o->v);
                insert(o->ch[d],x);
                if(((o->ch[d])->r)>(o->r))
                    rotate(o,d^1);
            }
        }
        o->maintain();
    }
    void del(Node* &o,int x){
        if(o->v==x){
            if(o->cnt>1){
                o->cnt--;
                o->s--;
            }else{
                if(o->ch[0]==null){
                    Node *u=o;
                    o=o->ch[1];
                    delete u;
                }else{
                    if(o->ch[1]==null){
                        Node *u=o;
                        o=o->ch[0];
                        delete u;
                    }else{
                        int d=(o->ch[1]->r)>(o->ch[0]->r);
                        rotate(o,d^1);
                        del(o->ch[d^1],x);
                    }
                }
            }
        }else{
            int d=x>(o->v);
            del(o->ch[d],x);
        }
        if(o!=null)
            o->maintain();
    }
    int kth(Node *o,int k){
        if(k<=(o->ch[0]->s)){
            return kth(o->ch[0],k);
        }else{
            k-=o->ch[0]->s;
            if(k<=o->cnt)
                return o->v;
            else
                return kth(o->ch[1],k-(o->cnt));
        }
    }
    int rank(Node *o,int x){
        if(o==null)
            return 0;
        if(x<(o->v)){
            return rank(o->ch[0],x);
        }else{
            if(x==o->v)
                return o->ch[0]->s+1;
            else
                return o->ch[0]->s+o->cnt+rank(o->ch[1],x);
        }
    }
    int pre(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v<x){
                ans=cur->v;
                cur=cur->ch[1];
            }else{
                cur=cur->ch[0];
            }
        }
        return ans;
    }
    int suc(int x){
        Node *cur=root;
        int ans=0;
        while(cur!=null){
            if(cur->v>x){
                ans=cur->v;
                cur=cur->ch[0];
            }else{
                cur=cur->ch[1];
            }
        }
        return ans;
    }
};
int main(){
    int n;
    int opt,x;
    Treap T;
    scanf("%d",&n);
    srand(20020601);
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1){
            T.insert(T.root,x);
        }else{
            if(opt==2){
                T.del(T.root,x);
            }else{
                if(opt==3){
                    printf("%d\n",T.rank(T.root,x));
                }else{
                    if(opt==4){
                        printf("%d\n",T.kth(T.root,x));
                    }else{
                        if(opt==5){
                            printf("%d\n",T.pre(x));
                        }else{
                            printf("%d\n",T.suc(x));
                        }
                    }
                }
            }
        }
    }
    return 0;
}


[COGS 396]魔术球问题(简化版)

2016年8月27日 22:55 | Comments(0) | Category:题解 | Tags:

这简化的真彻底……变成一个贪心水体了……

枚举柱子数,然后每次尽可能放球,放不了球了增加柱子,增加不了了就是最优解:

代码:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=61;
vector<int> V[maxn];
inline bool isSqr(int x){
    register int temp=floor(sqrt(x));
    return temp*temp==x;
}
int main(){
    int n,temp;
    bool flag;
    register int i,j,ans=1;
    freopen("balla.in","r",stdin);
    freopen("balla.out","w+",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        while(true){
            flag=false;
            for(j=0;j<i;j++){
                if(V[j].empty() || isSqr(V[j].back()+ans)){
                    V[j].push_back(ans++);
                    flag=true;
                    break;
                }
            }
            if(!flag)
                break;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

[COGS 729]圆桌聚餐

2016年8月27日 21:16 | Comments(0) | Category:题解 | Tags:

第一次做这种”大型“网络流题(抱歉我是炒鸡大局若)。

注意同一个单位的人不可同桌聚餐,说明同一单位的人最多只能往某一桌子派一人!然后建图就很简单了:源点往每个单位连流量为[tex]r_i[/tex]的边,每个单位分别向每一个桌连一条流量为1的边,每个桌向汇点连一条流量为[tex]c_i[/tex]的边。跑一遍网络流即可。

这题坑点在于要输出解。输出解的时候注意不要把反向弧和正常的弧搞混。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=425;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};
int main(){
    int n,m,temp;
    bool flag;
    register int i,j,tag,end,Expect=0;
    freopen("roundtable.in","r",stdin);
    freopen("roundtable.out","w+",stdout);
    scanf("%d%d",&n,&m);
    end=n+m+1;
    REP_B(i,n){
        scanf("%d",&temp);
        Expect+=temp;
        Dinic::AddEdge(0,i,temp);
    }
    REP_B(i,m){
        scanf("%d",&temp);
        tag=i+n;
        Dinic::AddEdge(tag,end,temp);
        REP_B(j,n){
            Dinic::AddEdge(j,tag,1);
        }
    }
    temp=Dinic::Maxflow(0,end);
    if(temp<Expect){
        puts("0");
        return 0;
    }
    puts("1");
    REP_B(i,n){
        vector<int> V;
        REP(j,Dinic::G[i].size()){
            Edge& e=Dinic::edges[Dinic::G[i][j]];
            if(e.v>n && e.v<=m+n && e.cap==e.flow)
                V.push_back(e.v);
        }
        sort(V.begin(),V.end());
        flag=false;
        REP(j,V.size()){
            if(flag)
                putchar(' ');
            flag=true;
            printf("%d",V[j]-n);
        }
        putchar('\n');
    }
    return 0;
}

[BZOJ 1196]公路修建问题

2016年8月27日 17:06 | Comments(0) | Category:题解 | Tags:

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 4326]运输计划

2016年8月26日 15:49 | Comments(0) | Category:题解 | Tags:

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的,有点吃不消,再加上会被卡常,咔嚓掉。

考虑二分答案。我们可以直接二分最终答案,那么如何验证?

假设验证谓词为[tex]C(t)[/tex],表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢?可以考虑树上差分,对于每次计划[tex](u,v)[/tex],我们求出其最近公共祖先[tex]L[/tex],然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一,对[tex]d[L][/tex]则减二。随后将d上标记上推,可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确:二分答案,树上差分验证,同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法,倍增也可。

代码:

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}