### Saratov State University :: Online Contester

::Go
- home
- news
- register
 - update personal info
 - problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- projects

 ::Poll Are you registered on Codeforces?YesNoWhat is it???[results]

::webboard

 WA on test 63
Author: keepcalmandsolve
ID: 055503
Problem: 534
Contest: 0
Date: 2014-12-31 21:26:39

I don't know where is my bug? Can anyone help?

//In the name of ALLAH

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stack>

using namespace std;

#define err(x) cout<<#x<<" : "<<x<<'n';;
typedef pair<int,int> pii;
typedef long long ll;
const ll N=100000+100;
const ll M=100000+100;
const ll INF=20000*1000*100;

//lp[0][i] = logest path in subtree 'i'
//lp[1][i] = second logest path in subtree 'i'
//t[e],p[e] = value for edge 'e'
//dep[i] = depth of vertex 'i'
//pe[i] = index of edge from 'i' to 'dad[i]'
//cntlp[i] = number of longest paths in subtree 'i'
//eans[i] = 'true':means the edge to its dad(dad[i]) must be removed, 'false':otherwise

int n;
ll ans[N];
bool eans[N];
stack <int> rmv;

void dfs(int v,int par=-1){
lp[0][v]=lp[1][v]=cntlp[v]=0;
dfs(u,v);
if (lp[0][v] < lp[0][u] + t[pe[u]]) lp[0][v] = lp[0][u] + t[pe[u]];
}

if (lp[1][v] < lp[0][u=adj[v][i].first] + t[pe[u]]){
if (lp[0][u] + t[pe[u]] < lp[0][v]) lp[1][v] = lp[0][u] + t[pe[u]];
else cntlp[v]++;
}
}

void solve (int v,int par){
ll sum=0;
bool isleaf=true;
isleaf=false;
}
sum += ans[u];

if (isleaf || p[pe[v]] < sum){
ans[v] = p[pe[v]];
eans[v] = true;
}
else{
ans[v]=sum;
eans[v] = false;
}
}

// finds for vertex 'v' the list of edge that must be deleted to reduce the diameter
void remove(int v){
if (eans[v]){
rmv.push(pe[v]); return;
}
remove(u);
}

int main(){
scanf("%d",&n);
for (int a,b,i=1;i<n;i++){
scanf("%d%d%I64d%I64d",&a,&b,t+i,p+i);
}

dep[0]=dep[1]=0;
dfs(1);
ll diam=0; int root=0;
for (int i=1;i<=n;i++){
if (cntlp[i]==1 && lp[0][i]+lp[1][i] > diam) diam = lp[0][i] + lp[1][i];
else if (cntlp[i]>1 && lp[0][i] * 2 > diam) diam = 2*lp[0][i];
}
for (int i=1;i<=n;i++){
if (cntlp[i]==1 && lp[0][i]+lp[1][i] == diam && dep[i]>=dep[root]) root=i;
else if (cntlp[i]>1 && lp[0][i]*2 == diam) root=i;
}

// now we have found the vertex 'root' which is in all of diametres
dfs(root); // --> updating values of lp[],... in the new tree rooted at vertex 'root'
solve(adj[root][i].first, root); // finds for each vertex 'i': the minimum cost we should pay to reduce longest path from subtree 'i'
}

int nlp[2]={0,0}; // nlp[0] = number of longest paths nlp[1] = number of second longest paths
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]) nlp[0]++ ;
if (lp[0][u] + t[pe[u]] == lp[1][root]) nlp[1]++;
}

ll res=0,maxi=-1;
if (nlp[0]>1){
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]){
res += ans[u];
maxi=max(maxi, ans[u]);
}
bool found=false;
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root] && ans[u]==maxi && !found) found=true;
else if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]) remove(u);
}

assert(maxi>0);
printf("%dn",res-maxi);
printf("%dn",(int)rmv.size());
int z;
while (!rmv.empty()){
z = rmv.top(); rmv.pop();
printf("%d ",z);
}
printf("n");
}
else {
assert(nlp[0]==1);

ll res2=0;
}

if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[1][root])
res += ans[u];

if (nlp[1]==0) res=INF;
printf("%dn",min(res,res2)); // min(res,res2) : we must destroy (all of second longest paths) OR (the longest path)

if (res<res2){
rmv.pop();
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[1][root])
remove(u);
}

printf("%dn",(int)rmv.size());
int z;
while (!rmv.empty()){
z = rmv.top(); rmv.pop();
printf("%d ",z);
}
printf("n");
}

return 0;
}