总结
最近写了好多树形dp+树形结构的题目，这些题目变化多样能与多种算法结合，但还是有好多规律可以找的。
先说总的规律吧！
一般来说树形dp在设状态转移方程时都可以用f[i][]表示i这颗子树怎么怎么样的最优解，实现时一般都是用子树更新父亲（即从下向上更新），那么首先应该考虑的是一个一个子树的更新父亲还是把所有子树都算完了在更新父亲？这就要因题而异了，一般来说有两种情况：1.需要把所有子树的信息都掌握之后再更新子树的就需要把所有子树都算完了在更新父亲。2.而像树上背包这样的问题就需要一个一个的更新，每次都用一个子树更新已经更新完的子树+父亲，最后就可以将这一部分的子树更新完了，再继续往上更新，最后根节点就是答案。
其实上面的两种情况可以总结成一种情况就是一个个子树更新父亲，一般来说第一种情况应用更多，也能解决第二情况的问题，只不过如果符合第二种情况的时候用第二种可以速度更快一点，毕竟你省了一遍循环嘛。
在分题型说说说说树形dp的规律！
1.子树和计数。
这类问题主要是统计子树和，通过加减一些子树满足题目中要求的某些性质。
1.codeforces 767C Garland
这道题是让你把树分成3部分，使每部分点权和相等，这就是通过算子树的size[]实现的。
2.洛谷1122最大子树和
这道题让你剪去一些子树，让剩下的子树点权和最大。这题就要维护子树的点权和，f[i]表示i这颗子树的点权和最大值。
2.树上背包问题
这类问题就是让你求在树上选一些点满足价值最大的问题，一般都可以设f[i][j]表示i这颗子树选j个点的最优解。
1.洛谷1272重建道路
这道题是让你剪去最少的边实现最后剩P个点。所以P个点就是背包，剪去的边数就是价值。这题需要转化一下把剪边变成加边。
2.洛谷1273有线电视网
这道题是让你在保证不亏损的情况下满足更多的客户看到转播。此时用户的个数就是容量，f[i][j]表示i这颗子树选j个用户能赚的最多的钱。
3.花费最少的费用覆盖所有点
这类问题是父亲与孩子有联系的题。基本有两种出法：1.选父亲必须不能选孩子（强制）2.选父亲可以不用选孩子（不强制）。 1.洛谷2458 [SDOI]保安站岗 这题就属于类型2.这就需要预估，要不要选这个节点的父亲。f[i][0]表示选自己，f[i][1]表示选孩子，f[i][2]表示选父亲。 2.UVA 1220Party at Hali-Bula（这是最大独立集问题，用做和上面题区分） 这题就是强制要求父亲和孩子不能同时选，但这题没有要求必须把所有点完全覆盖，只是让选尽可能多的点，所以这样就可以用f[i][0]表示选自己，f[i][1]表示选孩子,省去f[i][2]表示选父亲了，因为没有都覆盖的强制要求，他的父亲选不选可以到他父亲再判断。4.树上统计方案数问题
这类问题就是给你一个条件，问你有多少个点的集合满足这样的条件。这类题主要运用乘法原理，控制一个点不动，看他能做多少贡献。
1. 51nod1588幸运树。 问有多少个三元组满足幸运数字， 可以控制一个点不动，分成子树内，子树外两个部分，分别相乘就行了。可以看这个博客 。
与多种算法结合&&大模拟
这种题只能根据题目分析，然后随机应变了。1.洛谷3621 [APIO]风铃
把题目中的要求变成公式就行了。
2. 51nod1673树有几多愁
这道题是非常强的综合题，用到了虚树+状压dp+树形dp，具体的看这个博客吧。
3.51nod1531树上的博弈
非常强的一道博弈题。需要分情况的讨论，还是具体的看这个博客吧。
下面具体分析这几到例题。
1.codeforce 767CGarland
2.洛谷1122最大子树和
3.洛谷1272重建道路
4.洛谷1273有线电视网
5.洛谷2458 [SDOI]保安站岗
6.洛谷3621 [APIO]风铃
codeforce 767CGarland
Once at New Year Dima had a dream in which he was presented a fairy garland. A garland is a set of lamps, some pairs of which are connected by wires. Dima remembered that each two lamps in the garland were connected directly or indirectly via some wires. Furthermore, the number of wires was exactly one less than the number of lamps.
There was something unusual about the garland. Each lamp had its own brightness which depended on the temperature of the lamp. Temperatures could be positive, negative or zero. Dima has two friends, so he decided to share the garland with them. He wants to cut two different wires so that the garland breaks up into three parts. Each part of the garland should shine equally, i.e. the sums of lamps' temperatures should be equal in each of the parts. Of course, each of the parts should be non-empty, i.e. each part should contain at least one lamp.
Help Dima to find a suitable way to cut the garland, or determine that this is impossible.
While examining the garland, Dima lifted it up holding by one of the lamps. Thus, each of the lamps, except the one he is holding by, is now hanging on some wire. So, you should print two lamp ids as the answer which denote that Dima should cut the wires these lamps are hanging on. Of course, the lamp Dima is holding the garland by can't be included in the answer.
Input
The first line contains single integer n(3 ≤ n ≤ 106)— the number of lamps in the garland.
Thennlines follow. Thei-th of them contain the information about thei-th lamp: the number lampai, it is hanging on (and0, if is there is no such lamp), and its temperatureti( - 100 ≤ ti ≤ 100). The lamps are numbered from1 ton.
Output
If there is no solution, print -1.
Otherwise print two integers— the indexes of the lamps which mean Dima should cut the wires they are hanging on. If there are multiple answers, print any of them.
Examples
Input
62 40 54 22 11 14 2
Output
1 4
Input
62 40 64 22 11 14 2
Output
-1
Note
The garland and cuts scheme for the first example:
题目大意：把一颗树切成3部分，使得每一部分的点权和相等。
题解
很容易发现每一颗子树的点权是固定的，因为总和固定，设每一部分的大小为W，那么我们就从下往上更新，遇到等于W的子树就切一刀，sz重置成0，这就可以一边遍历子树，一边算sz.这题细节挺多的，需要注意一条链的情况和和三的倍数但不能分成几个相等的部分的情况。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1000100;int w[N],pre[N*2],last[N],other[N*2],num;inline void add(int x,int y){num++;pre[num]=last[x];last[x]=num;other[num]=y;}int n,root,sum,sz[N],cnt,ans[5];void dfs(int x,int fa){sz[x]=w[x];for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa){dfs(v,x);sz[x]+=sz[v];}}//if(cnt==2) {system("pause");exit(0);}if(sz[x]==sum) ans[++cnt]=x,sz[x]=0;}int main(){int x,y;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(x!=0) add(i,x),add(x,i);else root=i;w[i]=y;sum+=y;}if(sum%3!=0){puts("-1"); }else{sum/=3;dfs(root,0);//cout<<cnt<<endl;if(cnt<=2) puts("-1"); //等于二说明是一条链，只有两部分。 else printf("%d %d\n",ans[1],ans[2]);}return 0;}
洛谷1122最大子树和
题目描述
小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：
一株奇怪的花卉，上面共连有N 朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解。小明见问题被轻易攻破，相当不爽，于是又拿来问你。
输入输出格式
输入格式：
输入文件maxsum3.in的第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。
第二行有N 个整数，第I个整数表示第I朵花的美丽指数。
接下来N-1行每行两个整数a,b，表示存在一条连接第a 朵花和第b朵花的枝条。
输出格式：
输出文件maxsum3.out仅包括一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。
输入输出样例
输入样例#1：7-1 -1 -1 1 1 1 01 42 53 64 75 76 7
输出样例#1：
3
说明
【数据规模与约定】
对于60%的数据，有N≤1000；
对于100%的数据，有N≤16000。
题解
这题和上一题类似，都是求子树和。考虑如果子树的和为负，那么删掉它一定比不删掉它更优，用一个cut数组记录这个子树是否删去。注意这题不一定到根节点是最优的，所以要算一个子树更新一次。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;int n;const int N=20010;int pre[N*2],last[N],other[N*2],num,dp[N],a[N],ans;bool cut[N];inline void add(int x,int y){num++;pre[num]=last[x];last[x]=num;other[num]=y;}void tree_dp(int x,int fa){dp[x]=a[x];for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa)tree_dp(v,x);}for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa&&!cut[v])dp[x]+=dp[v]; }if(dp[x]<0) cut[x]=1;ans=max(ans,dp[x]);}int main(){int x,y;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);tree_dp(1,1);printf("%d\n",ans);return 0;}
洛谷1272重建道路
题目描述
一场可怕的地震后，人们用N个牲口棚(1≤N≤150，编号1..N)重建了农夫John的牧场。由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。因此，牧场运输系统可以被构建成一棵树。John想要知道另一次地震会造成多严重的破坏。有些道路一旦被毁坏，就会使一棵含有P(1≤P≤N)个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。
输入输出格式
输入格式：
第1行：2个整数，N和P
第2..N行：每行2个整数I和J，表示节点I是节点J的父节点。
输出格式：
单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。
输入输出样例
输入样例#1：11 61 21 31 41 52 62 72 84 94 104 11
输出样例#1：
2
说明
【样例解释】
如果道路1-4和1-5被破坏，含有节点（1，2，3，6，7，8）的子树将被分离出来
题解
这题就有一些难度了，主要是要转化一些问题。
我们发现这题意思就是删除一些边使原图剩P个节点，那么我们在进行树形dp的时候就要考虑这条是不是删,但这样就不太好转移。那么我们转化一下，假设把所有的边先都删除，那么我们要考虑这条边是不是要加进去，这要就好转移多了，就是一个裸地背包+树形dp。写的时候要判断是不是根节点。具体的转移方程写在代码里了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int inf=1e9+7;int n,p;const int N=200;int pre[N*2],last[N],other[N*2],num,ans=inf;int du[N],f[N][N];//f[i][j]表示在以i为根的子树里截取j个节点最少要删边数inline void add(int x,int y){num++;pre[num]=last[x];last[x]=num;other[num]=y;}void dfs(int x,int fa){f[x][1]=du[x]-(fa!=0);for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa){dfs(v,x);for(int j=p;j>=1;j--){for(int k=1;k<j;k++)f[x][j]=min(f[x][j],f[x][k]+f[v][j-k]-1);//为何要-1,因为一开始把所有的边都删了 }}}ans=min(ans,f[x][p]+(fa!=0));}int main(){int x,y;scanf("%d%d",&n,&p);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);du[x]++;du[y]++;}memset(f,0x3f,sizeof(f) );dfs(1,0);printf("%d\n",ans);return 0;}
洛谷1273有线电视网
题目描述
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
输入输出格式
输入格式：
输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。
第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：
K A1 C1 A2 C2 … Ak Ck
K表示该转播站下接K个结点(转播站或用户)，每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。
输出格式：
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
输入输出样例
输入样例#1：5 32 2 2 5 32 3 2 4 33 4 2
输出样例#1：
2
说明
样例解释
如图所示，共有五个结点。结点①为根结点，即现场直播站，②为一个中转站，③④⑤为用户端，共M个，编号从N-M+1到N，他们为观看比赛分别准备的钱数为3、4、2，从结点①可以传送信号到结点②，费用为2，也可以传送信号到结点⑤，费用为3（第二行数据所示），从结点②可以传输信号到结点③，费用为2。也可传输信号到结点④，费用为3（第三行数据所示），如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：
2+3+2+3=10，大于用户愿意支付的总费用3+4+2=9，有线电视网就亏本了，而只让③④两个用户看比赛就不亏本了。
题解
典型的树形dp+01背包。
f[i][j]表示i这个子树让j个用户转播所能赚的最多的钱。
f[i][j]=max(f[i][j],f[v][k]+f[i][j-k]-w[i]).注意要倒序循环，否则可能一个点被重复用了多次。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m;const int N=3010;int pre[N*2],last[N],other[N*2],num,w[N*2],v[N];int f[N][N],size[N],du[N];inline void add(int x,int y,int z){num++;pre[num]=last[x];last[x]=num;other[num]=y;w[num]=z;}void work(int x,int fa){f[x][0]=0;for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa){work(v,x);size[x]+=size[v];/*for(int j=size[x];j>=0;j--)//刷表法 for(int k=size[v];k>=0;k--)f[x][j+k]=max(f[x][j+k],f[x][j]+f[v][k]-w[i]); size[x]+=size[v];*/for(int j=size[x];j;j--)//填表法 必须倒序循环，否则会重复利用，如果压维就要倒序 for(int k=1;k<=min(j,size[v]);k++)f[x][j]=max(f[x][j],f[x][j-k]+f[v][k]-w[i]);//f[i][x][j]=f[i-1][x][j]+f[size[v]][v][k]-w[i];省去了第几个子树这一维 }}if(du[x]==1){f[x][1]=v[x];size[x]=1;}}int main(){int x,y,z;scanf("%d%d",&n,&m);memset(f,128,sizeof(f));for(int i=1;i<=n-m;i++){scanf("%d",&x);for(int j=1;j<=x;j++){scanf("%d%d",&y,&z);add(i,y,z);add(y,i,z);du[i]++;du[y]++;}}for(int i=n-m+1;i<=n;i++) scanf("%d",&v[i]);work(1,1);/* for(int j=1;j<=n;j++)for(int i=1;i<=m;i++)printf("f[%d][%d]=%d\n",j,i,f[j][i]);*/for(int i=m;i>=0;i--){if(f[1][i]>=0){printf("%d\n",i);break;}}return 0;}
洛谷2458 [SDOI]保安站岗
题目描述
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。
编程任务：请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。
输入输出格式
输入格式：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个通道端点的信息，依次为：该结点标号i（0<i<=n），在该结点安置保安所需的经费k（<=10000），该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。
对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。
输出格式：
最少的经费。
如右图的输入数据示例
输出数据示例：
输入输出样例
输入样例#1：61 30 3 2 3 42 16 2 5 63 5 04 4 05 11 06 5 0
输出样例#1：
25
说明
样例说明：在结点2，3，4安置3个保安能看守所有的6个结点，需要的经费最小：25
题解
这题是父亲与孩子有限制的树形dp。
由于这个点放不放保安与儿子放不放保安和父亲放不放保安都有关系，所以假设f[x][0] 自己选，f[x][1] 自己不选，儿子选，f[x][2] 自己不选，父亲选。dp不是没有后效性吗？为什么这个节点可以看他的父亲呢？其实是可以的，这个叫做未来计算，可以事先把还没发生但是肯定会发生的费用累加到答案中。那么这题就非常简单了。
dp方程：f[x][0]+=min(f[vv][1],min(f[vv][2],f[vv][0]));f[x][2]+=min(f[vv][0],f[vv][1]);dp[x][1]有一些特殊的地方因为自己不选儿子并不一定所有的儿子都选，所以我们要选一个最优的儿子选。可以记一个f[vv][0]-f[vv][1]的最小值，最后把这个加进去就行了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;int n;const int N=2000; const int inf=1e9;int pre[N*2],last[N],other[N*2],num;int f[N][5],v[N],du[N];//f[x][0] 自己选，f[x][1] 自己不选，儿子选，f[x][2] 自己不选，父亲选 inline void add(int x,int y){num++;pre[num]=last[x];last[x]=num;other[num]=y;}void dfs(int x,int fa){f[x][0]=v[x];//if(du[x]==1) f[x][0]=0;for(int i=last[x];i;i=pre[i]){int vv=other[i];if(vv!=fa){dfs(vv,x); }}bool yes=0,have=0;int minn=inf;for(int i=last[x];i;i=pre[i]){int vv=other[i];have=true;f[x][0]+=min(f[vv][1],min(f[vv][2],f[vv][0]));f[x][2]+=min(f[vv][0],f[vv][1]);if(f[vv][0]<=f[vv][1]){f[x][1]+=f[vv][0];yes=1; }else{f[x][1]+=f[vv][1];minn=min(minn,f[vv][0]-f[vv][1]);}}if(!yes) f[x][1]+=minn;if(!have) f[x][1]=inf;}int main(){int x,x1,y,z;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&z);v[x]=y;for(int i=1;i<=z;i++){scanf("%d",&x1);add(x,x1);add(x1,x);}}memset(f,0,sizeof(f));dfs(1,0);printf("%d\n",min(f[1][1],f[1][0]));return 0;}
洛谷3621[APIO]风铃
题目描述
你准备给弟弟 Ike 买一件礼物，但是，Ike 挑选礼物的方式很特别：他只喜欢那些能被他排成有序形状的东西。
你准备给 Ike 买一个风铃。风铃是一种多层的装饰品，一般挂在天花板上。
每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接，下面或者挂着另一根水平杆，或者挂着一个玩具。下面是一个风铃的例子：
为了满足弟弟，你需要选一个满足下面两个条件的风铃：
(1) 所有的玩具都在同一层(也就是说，每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。
(2) 对于两个相差一层的玩具，左边的玩具比右边的玩具要更靠下一点。
风铃可以按照下面的规则重新排列：任选一根杆，将杆两头的线“交换”。也就是解开一根杆左右两头的线，然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。
正在训练信息学奥林匹克的你，决定设计一个算法，判断能否通过重新排列，将一个给定的风铃变为 Ike 喜欢的样子。
考虑上面的例子，上图中的风铃满足条件(1)，却不满足条件(2)——最左边的那个玩具比它右边的要高。
但是，我们可以通过下面的步骤把这个风铃变成一个 Ike 喜欢的：
第一步，将杆 1 的左右两边交换，这使得杆 2 和杆 3 的位置互换，交换的结果如下图所示：
第二步，也是最后一步，将杆 2 的左右两边交换，这使得杆 4 到了左边，原来在左边的玩具到了右边，交换的结果发下图所示：
现在的这个风铃就满足 Ike 的条件了。
你的任务是：给定一个风铃的描述，求出最少需要多少次交换才能使这风铃满足 Ike 的条件(如果可能)
输入输出格式
输入格式：输入的第一行包含一个整数 n(1≤n≤100 000)，表示风铃中有多少根杆。
接下来的 n 行描述杆的连接信息。这部分的第 i 行包含两个由空格分隔的整数 li和 ri，描述杆 i 的左右两边悬挂的东西。如果挂的是一个玩具，则对应的值为-1，否则为挂在下面的杆的编号
输出格式：
输出仅包含一个整数。表示最少需要多少次交换能使风铃满足 Ike 的条件。如果不可能满足，输出-1。
输入输出样例
输入样例#1：6 2 3 -1 4 5 6 -1 -1 -1 -1 -1 -1
输出样例#1：
2
题解
一个树形dp的变形。
首先发现这个树一定是二叉树，根据邻接表的性质所以可以把左边的点最后加，这样边就是先左后右了。
设mindep[i]表示i这个点的子树中铃的最小深度，maxdep[i]表示最大深度。dp[i]表示使i这颗子树变成满足条件的需要几步，转移就是两个子树相加就行了，需要注意的是不满足的情况，除了深度差大于1，还有这个条件不要丢掉。maxdep[c[1]]>mindep[c[2]]&&maxdep[c[2]]>mindep[c[1]]。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>//#include<cmath>using namespace std;const int N=300010;int pre[N*2],last[N],other[N*2],num,w[N];int dep[N],mindep[N],maxdep[N],c[10],dp[N];inline void add(int x,int y){num++;pre[num]=last[x];last[x]=num;other[num]=y;}void dfs(int x,int fa){for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa){dep[v]=dep[x]+1;dfs(v,x);mindep[x]=min(mindep[x],mindep[v]);maxdep[x]=max(maxdep[x],maxdep[v]);}}if(w[x]==-1){mindep[x]=maxdep[x]=dep[x];}else{int cnt1=0;for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa)c[++cnt1]=v;}if((abs(maxdep[c[1]]-mindep[c[2]])>1)||(abs(mindep[c[1]]-maxdep[c[2]])>1) || (maxdep[c[1]]>mindep[c[2]]&&maxdep[c[2]]>mindep[c[1]])){puts("-1");exit(0);}dp[x]=dp[c[1]]+dp[c[2]]+((mindep[c[1]]<maxdep[c[2]])?1:0);}}void dfs1(int x,int fa){printf("%d ",x);for(int i=last[x];i;i=pre[i]){int v=other[i];if(v!=fa)dfs1(v,x);}}int main(){int n;int x,y;scanf("%d",&n);int cnt=n;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(y==-1) y=++cnt,w[cnt]=-1;add(i,y);add(y,i);if(x==-1) x=++cnt,w[cnt]=-1;add(i,x);add(x,i); }//cout<<other[last[2]]<<endl;memset(mindep,0x3f,sizeof(mindep));dfs(1,0);//if(maxdep[1]-mindep[1]>1) puts("-1"); printf("%d\n",dp[1]);return 0;}
