emmm
dpdpdp然鹅我考场上并想不到
还是凉凉
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #define rint register int using std::min; template <class T>inline void read(T &X) { X=0;int W=0;char ch=0; while(!isdigit(ch))W|=ch=='-',ch=getchar(); while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); X=W?-X:X;return; } int n,cnt=0,head[1000010]; long long dp[1000010][3],dis[1000010]; bool mark[1000010]; struct node {int to,next;long long w;}edge[2000010]; inline void add(int u,int v,long long w) { edge[++cnt].next=head[u]; edge[cnt].to=v; edge[cnt].w=w; head[u]=cnt; } void dfs(int u) { mark[u]=1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; if(mark[v]) continue; mark[v]=1; dfs(v); if(dis[v]+edge[i].w>dis[u]) dis[u]=dis[v]+edge[i].w; //每条边至少走过一次 dp[u][0]+=dp[v][0]+edge[i].w*2; //门两边都不在 这条边自然走两遍XD dp[u][1]+=min(dp[v][0]+edge[i].w-dis[v], dp[v][1]+edge[i].w*2); //1.[v][0]-d[v]是因为 [v][0]+了两次子节点的边 而其实 由于传送门 只用走一次。 //2.v有传送门时 由于只有两个传送门 所以u的传送门其实是下面的传上来的 u和v之间并没有传送门！！ } } int main() { freopen("portal.in","r",stdin); freopen("portal.out","w",stdout); read(n); for(rint i=1;i<n;i++) { int u,v; long long w; read(u),read(v),read(w); add(u,v,w); add(v,u,w); } dfs(1); printf("%lld",min(dp[1][0],dp[1][1])); return 0; }