SHARE
TWEET

Untitled

a guest Jul 9th, 2015 444 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector<int> adj[200200];
  7. vector<long long> edg[200200];
  8.  
  9. long long dp[200200];
  10. long long r[200200];
  11. long long l[200200];
  12. bool vis[200200];
  13. int n;
  14. int a,b,c;
  15. int t;
  16. void is_tree(int nd,int p){
  17.         if(vis[nd])while(1);
  18.         vis[nd]=true;
  19.         for(int i=0;i<adj[nd].size();i++){
  20.                 if(adj[nd][i]==p)continue;
  21.                 is_tree(adj[nd][i],nd);
  22.         }
  23. }
  24. void d(int nd,int p){
  25.         for(int i=0;i<adj[nd].size();i++){
  26.                 int ch=adj[nd][i];
  27.                 if(ch==p){
  28.                         adj[nd].erase(adj[nd].begin()+i);
  29.                         edg[nd].erase(edg[nd].begin()+i);
  30.                 }
  31.                
  32.         }
  33.         for(int i=0;i<adj[nd].size();i++){
  34.                 int ch=adj[nd][i];
  35.                 d(ch,nd);
  36.         }
  37. }
  38. void dfs1(int nd){
  39.         dp[nd]=0;
  40.         for(int i=0;i<adj[nd].size();i++){
  41.                 int ch=adj[nd][i];
  42.                 dfs1(ch);
  43.                 dp[nd]=max(dp[nd],dp[ch]+edg[nd][i]);
  44.         }
  45. }
  46. void dfs2(int nd,long long up){
  47.         dp[nd]=max(dp[nd],up);
  48.         int k=adj[nd].size();
  49.         for(int i=0;i<k;i++){
  50.                 int ch=adj[nd][i];
  51.                 if(i==0){
  52.                         l[ch]=dp[ch]+edg[nd][i];
  53.                 } else {
  54.                         int pr=adj[nd][i-1];
  55.                         l[ch]=max(l[pr],dp[ch]+edg[nd][i]);
  56.                 }
  57.         }
  58.         for(int i=k-1;i>=0;i--){
  59.                 int ch=adj[nd][i];
  60.                 if(i==k-1){
  61.                         r[ch]=dp[ch]+edg[nd][i];
  62.                 } else {
  63.                         int nxt=adj[nd][i+1];
  64.                         r[ch]=max(r[nxt],dp[ch]+edg[nd][i]);
  65.                 }
  66.         }
  67.         for(int i=0;i<k;i++){
  68.                 int ch=adj[nd][i];
  69.                 long long best=up;
  70.                 if(i!=0){
  71.                         best=max(best,l[adj[nd][i-1]]);
  72.                 }
  73.                 if(i!=k-1){
  74.                         best=max(best,r[adj[nd][i+1]]);
  75.                 }
  76.                 dfs2(ch,best+edg[nd][i]);
  77.         }
  78. }
  79.  
  80. int main(){
  81.         //cin>>t;
  82.         scanf("%d",&t);
  83.         if(t>10)while(1);
  84.         while(t--){
  85.                 //cin>>n;
  86.                 scanf("%d",&n);
  87.                 if(n<2 || n>100000)while(1);
  88.                 for(int i=1;i<=n;i++){
  89.                         dp[i]=0;
  90.                         l[i]=0;
  91.                         r[i]=0;
  92.                         adj[i].clear();
  93.                         edg[i].clear();
  94.                         vis[i]=false;
  95.                 }
  96.                 for(int i=2;i<=n;i++){
  97.                         //cin>>a>>b>>c;
  98.                         scanf("%d %d %d",&a,&b,&c);
  99.                         if(a<1 || a>n)while(1);
  100.                         if(b<1 || b>n)while(1);
  101.                         adj[a].push_back(b);
  102.                         adj[b].push_back(a);
  103.                         edg[a].push_back(c);
  104.                         edg[b].push_back(c);
  105.                 }
  106.                 is_tree(1,1);
  107.                 for(int i=1;i<=n;i++){
  108.                         if(!vis[i])while(1);
  109.                 }
  110.                 d(1,1);
  111.                 dfs1(1);
  112.                 dfs2(1,0);
  113.                 for(int i=1;i<n;i++){
  114.                         //cout<<dp[i]<<" ";
  115.                         printf("%lld ",dp[i]);
  116.                 }
  117.                 //cout<<dp[n]<<endl;
  118.                 printf("%lld\n",dp[n]);
  119.         }
  120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top