Dfs的时候让所有叶子结点与n+1结点建边，然后跑rt和n+1之间的dinic，结果tle比较重，不知道怎么优化，求指导。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define INF 1e18
#define maxv 100500
#define maxe 300500
#define maxlogv 10 
#define rep(i,a,n) for(register int i=a;i<n;++i)
typedef long long ll;
using namespace std;
ll n,m,q,u,v,w,s,t,rt;
namespace network_flow{ 
    struct edge{
        ll to,next,flow;
    }E[maxe<<2];
    int head[maxv];
    int deep[maxv];
    int sz=1;
    void add(ll u,ll v,ll w){
        E[++sz]={v,head[u],w};
        head[u]=sz;
        E[++sz]={u,head[v],0};
        head[v]=sz;
    }
    bool bfs(ll s,ll t){
        memset(deep,0,sizeof(deep));
        deep[s]=1;
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=E[i].next){
                int y=E[i].to;
                if(!deep[y]&&E[i].flow){
                    deep[y]=deep[x]+1;
                    q.push(y);
                }
            }
        }
        return deep[t]!=0;
    }
    ll dfs(ll x,ll t,ll minf){
        if(x==t) return minf;
        ll k,rest=minf;
        for(int i=head[x];i;i=E[i].next){
            int y=E[i].to;
            if(deep[y]==deep[x]+1&&E[i].flow){
                k=dfs(y,t,min(rest,E[i].flow));
                rest-=k;
                E[i].flow-=k;
                E[i^1].flow+=k;
                if(k==0) deep[y]=0;
                if(rest==0) break;
            }
        } 
        return minf-rest;
    }
    void init(){
        for(int i=2;i<=sz;i+=2){
            E[i].flow=(E[i].flow+E[i^1].flow);
            E[i^1].flow=0;
        }
    }
    ll dinic(ll s,ll t){
        init();
        ll ans=0,now=0;
        while(bfs(s,t)){
            while(now=dfs(s,t,INF)) ans+=now;
        }
        return ans;
    }
    void Dfs(ll x,ll t,ll fa){
		bool flag=1;
		for(int i=head[x];i;i=E[i].next){
			ll to=E[i].to;
			if(to!=fa && to!=t) flag=0,Dfs(to,t,x);
		}
		if(flag) add(x,t,INF);
	}
} 

int main(){
	cin>>n>>rt;
	rep(i,1,n){
		cin>>u>>v>>w;
		network_flow::add(u,v,w);
		network_flow::add(v,u,w);
	}
	network_flow::Dfs(rt,n+1,0ll);				//空汇点与叶子结点建边 
	cout<<network_flow::dinic(rt,n+1);
	return 0;
}