悬赏关注加赞博客

#include<bits/stdc++.h>
using namespace std;
struct node {
	int p,w;
	node(int a,int b) {
		p=a,w=b;
	}
};
vector<node> a[2005];
int n,q,u,v,w,s,k,t,c[2005],book[2005],ans=1<<30;
void dfs(int p,int bs,int bl,int zt) {
	if(bs>=ans)return;
	if(bl==n) {
		ans=min(ans,bs);
		return;
	}
	for(int i=0; i<a[p].size(); i++) {
		int np=a[p][i].p;
		if(np==t&&zt==0)continue;
		if(book[np]<c[np]) {
			if(book[np]==0)bl++;
			if(np==k)zt=1;
			book[np]++;
			dfs(np,bs+a[p][i].w,bl,zt);
			book[np]--;
			if(book[np]==0)bl--;
			if(np==k)zt=0;
		}
	}
}
int main() {
	cin>>n>>q;
	for(int i=1; i<=n-1; i++) {
		cin>>u>>v>>w;
		a[u].push_back(node(v,w));
		a[v].push_back(node(u,w));
		c[v]++,c[u]++;
	}
	while(q--) {
		cin>>s>>k>>t;		
		if(book[s]<c[s]) {
		    int bl=0,zt=0;
			if(book[s]==0)bl++;
			if(s==k)zt=1;
			book[s]++;
			dfs(s,0,bl,zt);
			book[s]--;
			if(book[s]==0)bl--;
			if(s==k)zt=0;
		}
		if(ans!=1<<30)cout<<ans<<endl,ans=1<<30;
		else cout<<"impossible"<<endl;
	}
	return 0;
}
/*
3 1
3 1 1 
1 2 1
2 1 3
*/