Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAXN 100000
- #define mp make_pair
- #define pb push_back
- using namespace std;
- int n; // Vertices
- int G[MAXN][MAXN]; // Grafo
- //vector<int> grafo[MAXN];
- //map<pair<int,int>,int> grafo;
- //set<int> bip[2];
- int C[MAXN],vis[MAXN]; // Cores
- int counter[MAXN];
- int cor[3];
- bool bipartite(int v, int c) {
- C[v] = c;
- cor[c]++;
- int a = c;
- bool ret = true;
- c = c == 1? 2 : 1;
- for (int u = 0; u < n; u++) {
- if (G[v][u]) {
- if (!C[u]) ret = bipartite(u, c);
- else if (C[u] == a) return false;
- if (!ret) return false;
- }else{
- grafo.erase(mp(v,u));
- }
- }
- return ret;
- }
- int main(){
- scanf("%d",&n);
- memset(counter,0,sizeof counter);
- for(int i=0;i<n-1;i++){
- int x,y;
- scanf("%d %d",&x,&y);
- x--;
- y--;
- //grafo[x-1].pb(y-1);
- //grafo[y-1].pb(x-1);
- G[x][y]=true;
- G[y][x]=true;
- //grafo[mp(x-1,y-1)] = 1;
- //grafo[mp(y-1,x-1)] = 1;
- if(!C[x]){
- }
- counter[x]++;
- counter[y]++;
- }
- cor[0] = cor[1] = cor[2] = 0;
- for(int i=0;i<n;i++)
- if(!C[i])
- bipartite(i,1);
- //printf("%d %d %d\n",cor[0],cor[1],cor[2] );
- int ans1=0,ans2 =0;
- for(int i=0;i<n;i++){
- //printf("%d %d %d\n",C[i],cor[(C[i]%2)+1],counter[i] );
- if(C[i] == 1){
- ans1+= (cor[2] - counter[i]);
- }else{
- ans2+=(cor[1] - counter[i]);
- }
- }
- printf("%d\n",max(ans1,ans2) );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement