#include using namespace std; typedef long long ll; typedef pair pll; #define For(i, a, n) for(ll i=a;i pairoperator+(const pair&a, const pair&b){ return {a.first + b.first, a.second + b.second}; } template ostream&operator<<(ostream&os, const pair&p){ return os<<"("< basic_ostream&operator<<(basic_ostream&os, const C&c){ for(auto i=begin(c);i!=end(c);++i){ os<<(i==begin(c)?"":" ")<<*i; } return os; } template void dbg(Args&&... args){ ((cerr<& counts, vec>& children, vec& values, ll start){ for(ll i = 0; i < children[start].size(); i++){ countlanterns(counts,children,values,children[start][i]); counts[start] += counts[children[start][i]]; } if(values[start]){ counts[start]++; } } void f(ll pos, vec>& solution, vec>& children, vec& parents, vec& v, vec& goal){ //excess children for(ll i = 0; i < children[pos].size(); i++){ ll child = children[pos][i]; if(v[child] <= 0){ continue; } f(child,solution,children,parents,v,goal); } //take for(ll i = 0; i < children[pos].size(); i++){ ll child = children[pos][i]; if(v[child] > 0){ solution.push_back({{child,pos},v[child]}); } } //give for(ll i = 0; i < children[pos].size(); i++){ ll child = children[pos][i]; if(v[child] < 0){ solution.push_back({{pos,child},-v[child]}); } } //carrying children for(ll i = 0; i < children[pos].size(); i++){ ll child = children[pos][i]; if(v[child] > 0){ continue; } if(goal[child]){ f(child,solution,children,parents,v,goal); } } //non-carrying children for(ll i = 0; i < children[pos].size(); i++){ ll child = children[pos][i]; if(v[child] > 0){ continue; } if(!goal[child]){ f(child,solution,children,parents,v,goal); } } } void solve(){ ll n; cin >> n; vec> neigh(n); for(ll i = 0; i < n-1; i++){ ll a,b; cin >> a >> b; neigh[a].push_back(b); neigh[b].push_back(a); } ll k; cin >> k; vec lanterns1(n,false); vec lanterns2(n,false); for(ll i = 0; i < k; i++){ ll x; cin >> x; lanterns1[x] = true; } for(ll i = 0; i < k; i++){ ll x; cin >> x; lanterns2[x] = true; } vec parent(n,-2); parent[0] = -1; vec> children(n); vec frontier = {0}; while(!frontier.empty()){ ll pos = frontier.back(); frontier.pop_back(); for(ll i = 0; i < neigh[pos].size(); i++){ if(neigh[pos][i] == parent[pos]){ continue; } children[pos].push_back(neigh[pos][i]); parent[neigh[pos][i]] = pos; frontier.push_back(neigh[pos][i]); } } vec count1(n,0); vec count2(n,0); countlanterns(count1,children,lanterns1,0); countlanterns(count2,children,lanterns2,0); vec v(n); for(ll i = 0; i < n; i++){ v[i] = count1[i] - count2[i]; } vec> solution; f(0,solution,children,parent,v, lanterns2); cout << solution.size() << "\n"; for(ll i = 0; i < solution.size(); i++){ cout << solution[i].first.first << " " << solution[i].first.second << " " << solution[i].second << "\n"; } } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); ll t = 1;//cin>>t; while(t--)solve(); }