Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
87430433 Practice:
mshiladityam
1156D - 11 GNU C++17 (64) Accepted 873 ms 78500 KB 2020-07-20 15:45:01 2020-07-20 15:45:01
 
 
→ Source
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
#define int long long int
using namespace std;
int n;
vector<vector<int>> adj;
int dp[200001][2]={0}, num[200001][2]={0};
map<pair<int,int>, int> c;
void DFS1(int v, int par)
{
	for (int j=0; j<adj[v].size(); j++)
	{
		int u=adj[v][j];
		if (u!=par)
		{
			DFS1(u, v);
			if (c[{u, v}])
			{
				dp[v][1]+=1+dp[u][1];
			}
			else
			{
				dp[v][0]+=1+dp[u][0]+dp[u][1];
			}
		}
	}
	return;
}
void DFS2(int v, int par)
{
	if (par)
	{
		num[v][1]=dp[v][1];
		if (c[{v, par}])
		{
			num[v][1]+=num[par][1]-(dp[v][1]);
		}
		num[v][0]=dp[v][0];
		if (!c[{v, par}])
		{
			num[v][0]+=num[par][0]+num[par][1]-(dp[v][1]+dp[v][0]);
		}
	}
	for (int j = 0; j < adj[v].size(); j++)
	{
		int u = adj[v][j];
		if (u != par)
		{
			DFS2(u, v);
		}
	}
}
int solve()
{
	cin>>n;
	adj.resize(n + 1);
	for (int j=0; j<n-1; j++)
	{
		int v1, v2, d; cin>>v1>>v2>>d;
		adj[v1].push_back(v2);
		adj[v2].push_back(v1);
		c[{v1, v2}]=d;
		c[{v2, v1}]=d;
	}
	DFS1(1, 0);
	num[1][0]=dp[1][0];
	num[1][1]=dp[1][1];
	DFS2(1, 0);
	int ans=0;
	//cout << "\n";
	for (int j=1; j<=n; j++)
	{
		//cout << j<<" "<<num[j][0] << " " << num[j][1] << "\n";
		ans += num[j][0] + num[j][1];
	}
	cout<<ans<<"\n";
	return 0;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	//cin >> t;
	t=1;
	while (t--)
	{
		solve();
	}
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details