比赛 20110725 评测结果 AWWWAWWAAAWAAAAAWWAA
题目名称 存在与否 最终得分 60
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-25 12:56:16
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long s64;
const int MAXN=1005;
const s64 oo=~0u>>1;
#define pb push_back
#define mp make_pair
typedef pair<int,int> Pair;
typedef vector<Pair>::iterator Ptr;

vector<Pair> adj[MAXN];
inline void addedge(int u,int v,int w)
{
	adj[u].pb(mp(v,w));
	adj[v].pb(mp(u,w));
}

int L[MAXN],R[MAXN];
inline bool cmp(const Pair &u,const Pair &v)
{
	return L[u.first]<L[v.first];
}

int to[MAXN],father[MAXN];
void dfs(int u)
{
	if (to[u]!=0)
	{
		L[u]=to[u];
		R[u]=to[u];
	}
	else
	{
		int v;
		for(Ptr it=adj[u].begin();it!=adj[u].end();)
			if ((v=it->first)!=father[u])
			{
				father[v]=u;
				dfs(v);
				it++;
			}
			else
				it=adj[u].erase(it);
		sort(adj[u].begin(),adj[u].end(),cmp);
		L[u]=L[adj[u].front().first];
		R[u]=R[adj[u].back().first];
	}
}

int sum[MAXN];
s64 d[MAXN][3];
void dp(int u)
{
	if (to[u]!=0)
		d[u][0]=d[u][1]=d[u][2]=0;
	else
	{
		int v;
		s64 sigma=0;
		for(Ptr it=adj[u].begin();it!=adj[u].end();it++)
			if ((v=it->first)!=father[u])
			{
				dp(v);
				sigma+=d[v][0];
			}
		d[u][0]=oo;
		int k,j=adj[u].front().first;
		s64 tj=d[j][1]-d[j][0]+adj[u].front().second+sum[R[j]];
		s64 t;
		for(Ptr it=++adj[u].begin();it!=adj[u].end();it++)
			if ((k=it->first)!=father[u])
			{
				s64 tk=d[k][2]-d[k][0]+it->second-sum[L[k]];
				if ((t=sigma+tk+tj)<d[u][0])
					d[u][0]=t;
				tj=d[k][1]-d[k][0]+it->second+sum[R[k]];
				j=k;
			}
		v=adj[u].back().first;
		d[u][1]=sigma-d[v][0]+d[v][1]-(sum[R[u]]-sum[R[v]])+adj[u].back().second;
		v=adj[u].front().first;
		d[u][2]=sigma-d[v][0]+d[v][2]-(sum[L[v]]-sum[L[u]])+adj[u].front().second;
	}
}

int N,M;
int main()
{
	freopen("exists.in","r",stdin);
	freopen("exists.out","w",stdout);
	scanf("%d",&N);
	int tot=0;
	for(int i=0;i<N-1;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
		tot+=w;
	}
	scanf("%d",&M);
	for(int i=1;i<M+2;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		to[v]=i;
		sum[i]=sum[i-1]+w;
		tot+=w;
	}
	dfs(1);
	dp(1);
	if (d[1][0]>tot)
		printf("-1\n");
	else
		printf("%d\n",(int)(d[1][0]+sum[M+1]));
	return 0;
}