fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define ll long long int
  4. #define rep(i,a,b) for(ll i=a;i<b;i++)
  5. #define sep(i,b,a) for(ll i=b-1;i>=a;i--)
  6. #define hell (ll)(1e9+7)
  7.  
  8. using namespace std;
  9.  
  10. vector <ll> adj[100005];
  11. vector <bool> visited(100005,false);
  12. vector <pair<ll,ll> > vp(100005);
  13.  
  14. ll ans=0;
  15.  
  16. ll help(vector <ll> &v)
  17. {
  18.     vector < pair <ll,ll> > a;
  19.     rep(i,0,v.size())
  20.         a.push_back(vp[v[i]]);
  21.     sort(a.begin(),a.end());
  22.     vector <ll> d(a.size()),t(a.size());
  23.     rep(i,0,a.size())
  24.     {
  25.         d[i]=a[i].first;
  26.         t[i]=a[i].second;
  27.     }
  28.     rep(i,1,a.size())
  29.         d[i]+=d[i-1];
  30.     ll s=0;
  31.     s+=d[0];
  32.     rep(i,1,a.size())
  33.     {
  34.         s+=t[i-1];
  35.         if(s<d[i])
  36.             s=d[i];
  37.     }
  38.     s+=t.back();
  39.     return s;
  40. }
  41.  
  42. void bfs()
  43. {
  44.     queue <ll> q;
  45.     q.push(1);
  46.     visited[1]=true;
  47.     while(!q.empty())
  48.     {
  49.         int n=q.size();
  50.         vector <ll> v;
  51.         rep(i,0,n)
  52.         {
  53.             ll s=q.front();
  54.             q.pop();
  55.             v.push_back(s);
  56.             rep(j,0,adj[s].size())
  57.             {
  58.                 if(!visited[adj[s][j]])
  59.                 {
  60.                     q.push(adj[s][j]);
  61.                     visited[adj[s][j]]=true;
  62.                 }
  63.             }
  64.         }
  65.         ll x=help(v);
  66.         //cout<<x<<"\n";
  67.         ans+=x;
  68.     }
  69. }
  70.  
  71. void init()
  72. {
  73.     rep(i,0,100005)
  74.     {
  75.         adj[i].clear();
  76.         visited[i]=false;
  77.     }
  78.     ans=0;
  79. }
  80.  
  81. void solve()
  82. {
  83.     ll n,u,v;
  84.     cin>>n;
  85.     init();
  86.     rep(i,0,n-1)
  87.     {
  88.         cin>>u>>v;
  89.         adj[u].push_back(v);
  90.         adj[v].push_back(u);
  91.     }
  92.     rep(i,1,n+1)
  93.     {
  94.         cin>>u>>v;
  95.         vp[i]={u,v};
  96.     }
  97.     bfs();
  98.     cout<<ans<<"\n";
  99. }
  100.  
  101. int main()
  102. {
  103. 	ios_base::sync_with_stdio(0);
  104. 	cin.tie(0);
  105. 	cout.tie(0);
  106. 	ll t;
  107. 	cin>>t;
  108. 	//t=1;
  109. 	while(t--)
  110. 	{
  111. 		solve();
  112. 	}
  113. 	return 0;
  114. }
  115.  
Success #stdin #stdout 0s 17720KB
comments (?)
stdin
copy 
1

7

1 2

1 3

2 4 

2 5

3 6

3 7

1 2

3 4

5 6

7 8

9 10

11 12

13 14
stdout
copy 
71
https://ideone.com/Rbk5cR
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!