题意
http://codeforces.com/contest/1189/problem/D2
思考
显然地，如果出现度数为2且两条出边边权不相同的情况，是无法构造合法方案的。
下面考虑缩边后的树，此时每个非叶子节点的度数一定大于等于3。
枚举每个非叶子节点，将其重新作为树的根，并尝试将它所有的出边都达到要求。我们先找到它代表的所有叶子，分两种情况考虑：
1.一条边以下只有一个叶子。如下图所示，红色的路径代表+w/2，w为该边的边权，蓝色路径代表-w/2，能达到平衡。
2.一条边以下不止一个叶子。如下图所示，我们要求选定边的子树中挑出的两个叶子的lca的深度必须最大，否则无法消除影响。此处可以挑选dfn最大和最小的那两个。
总复杂度O(n^2)。注意特判一条链的情况。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2E3+5; 4 int n; 5 int deg[maxn*2],hh[maxn]; 6 int tot,haha; 7 bool dot[maxn]; 8 vector<int>what[maxn]; 9 vector<int>wait; 10 double w[maxn]; 11 map<pair<int,int>,bool>vis; 12 inline pair<int,int>M(int x,int y) 13 { 14 if(x>y) 15 swap(x,y); 16 return make_pair(x,y); 17 } 18 struct edge 19 { 20 int to,next; 21 double w; 22 }; 23 struct note 24 { 25 int x,y; 26 double d; 27 note(int a=0,int b=0,double c=0) 28 { 29 x=a,y=b,d=c; 30 } 31 }; 32 vector<note>ans; 33 struct graph 34 { 35 int head[maxn*2],size; 36 edge E[maxn*2]; 37 inline void add(int u,int v,double w) 38 { 39 E[++size].to=v; 40 E[size].next=head[u]; 41 E[size].w=w; 42 head[u]=size; 43 } 44 void get(int u,int F,int num) 45 { 46 for(int i=head[u];i;i=E[i].next) 47 { 48 int v=E[i].to; 49 if(v==F) 50 continue; 51 if(u==F) 52 { 53 w[++num]=E[i].w; 54 hh[num]=v; 55 get(v,u,num); 56 } 57 else 58 get(v,u,num); 59 } 60 if(deg[u]==1) 61 what[num].push_back(u); 62 if(u==F) 63 for(int i=1;i<=num;++i) 64 { 65 if(vis[M(u,hh[i])]) 66 continue; 67 if(what[i].size()==1) 68 { 69 int u1=what[i][0]; 70 int x=what[i+1<=num?i+1:i+1-num][0]; 71 int y=what[i+2<=num?i+2:i+2-num][0]; 72 double d=w[i]/2; 73 ans.push_back(note(u1,x,d)); 74 ans.push_back(note(u1,y,d)); 75 ans.push_back(note(x,y,-d)); 76 vis[M(u,hh[i])]=1; 77 } 78 else 79 { 80 int u1=what[i][0],u2=what[i][what[i].size()-1]; 81 int x=what[i+1<=num?i+1:i+1-num][0]; 82 int y=what[i+2<=num?i+2:i+2-num][0]; 83 double d=w[i]/2; 84 ans.push_back(note(u1,x,d)); 85 ans.push_back(note(u2,y,d)); 86 ans.push_back(note(u1,u2,-d)); 87 ans.push_back(note(x,y,-d)); 88 vis[M(u,hh[i])]=1; 89 } 90 } 91 } 92 void find(int u,int F,int last) 93 { 94 dot[u]=1; 95 if(deg[u]!=2) 96 { 97 haha=last; 98 wait.push_back(u); 99 return; 100 } 101 for(int i=head[u];i;i=E[i].next) 102 { 103 int v=E[i].to; 104 if(v==F) 105 continue; 106 if(last==1) 107 { 108 find(v,u,E[i].w); 109 last=E[i].w; 110 } 111 else if(last==E[i].w) 112 find(v,u,E[i].w); 113 else 114 { 115 cout<<"NO"<<endl; 116 exit(0); 117 } 118 } 119 } 120 int sum; 121 void getsize(int u,int F) 122 { 123 ++sum; 124 for(int i=head[u];i;i=E[i].next) 125 { 126 int v=E[i].to; 127 if(v==F) 128 continue; 129 getsize(v,u); 130 } 131 } 132 }source,G; 133 int main() 134 { 135 ios::sync_with_stdio(false); 136 cin>>n; 137 for(int i=2;i<=n;++i) 138 { 139 int x,y; 140 double z; 141 cin>>x>>y>>z; 142 source.add(x,y,z); 143 source.add(y,x,z); 144 ++deg[x],++deg[y]; 145 } 146 int P1=1,P2=2; 147 for(int u=1;u<=n;++u) 148 { 149 if(deg[u]==2) 150 { 151 if(!dot[u]) 152 { 153 source.find(u,u,1); 154 wait.clear(); 155 G.add(wait[0],wait[1],haha); 156 G.add(wait[1],wait[0],haha); 157 P1=wait[0],P2=wait[1]; 158 } 159 continue; 160 } 161 for(int i=source.head[u];i;i=source.E[i].next) 162 { 163 int v=source.E[i].to; 164 haha=source.E[i].w; 165 if(deg[v]!=2) 166 G.add(u,v,source.E[i].w); 167 } 168 } 169 cout<<"YES"<<endl; 170 G.getsize(P1,P1); 171 if(G.sum==2) 172 { 173 cout<<1<<endl; 174 cout<<P1<<" "<<P2<<" "<<haha<<endl; 175 return 0; 176 } 177 for(int u=1;u<=n;++u) 178 { 179 if(deg[u]==1) 180 continue; 181 for(int i=1;i<=n;++i) 182 what[i].clear(); 183 G.get(u,u,0); 184 } 185 int del=0; 186 for(int i=0;i<ans.size();++i) 187 if(abs(ans[i].d-0)<=0.01) 188 ++del; 189 cout<<ans.size()-del<<endl; 190 for(int i=0;i<ans.size();++i) 191 if(abs(ans[i].d-0)>0.01) 192 cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].d<<endl; 193 return 0; 194 }