DFS solution O(n)

flipkart
Tags: #<Tag:0x00007f242a47cb60>

#1

vector<vector> g;
vector mark;
vector a;
const int mod=1e9+7;
vector sz;
long long int ans=0,sum=0;
void dfs(int u)
{
mark[u]=true;
for(auto v:g[u])
{
if(mark[v]==false)
{
dfs(v);
sz[u]+=sz[v];
}
}
sz[u]+=a[u-1];
ans = max(ans,(sum%mod-sz[u]%mod+mod)%mod*sz[u]%mod)%mod;
}
int Solution::deleteEdge(vector &A, vector<vector > &B) {
int n;
n=A.size();
a.resize(n);
sz.assign(n+1,0);
g.assign(n+1,vector());
mark.assign(n+1,false);
ans=0;
sum=0;
for(int i=0;i<n;i++)
{
a[i]=A[i];
sum+=a[i];
}
for(int i=0;i<n-1;i++)
{
int x,y;
x=B[i][0];
y=B[i][1];
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);

return ans%mod;

}


#2

First you should write your variable names so that other person can understand . If you cannot please don’t post such code.