题意

---

 

思考

显然地，如果出现度数为2且两条出边边权不相同的情况，是无法构造合法方案的。

下面考虑缩边后的树，此时每个非叶子节点的度数一定大于等于3。

枚举每个非叶子节点，将其重新作为树的根，并尝试将它所有的出边都达到要求。我们先找到它代表的所有叶子，分两种情况考虑：

1.一条边以下只有一个叶子。如下图所示，红色的路径代表+w/2，w为该边的边权，蓝色路径代表-w/2，能达到平衡。

2.一条边以下不止一个叶子。如下图所示，我们要求选定边的子树中挑出的两个叶子的lca的深度必须最大，否则无法消除影响。此处可以挑选dfn最大和最小的那两个。

总复杂度O(n^2)。注意特判一条链的情况。

---

 

代码

1 #include
      
         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
       
        what[maxn];  9 vector
        
         wait; 10 double w[maxn]; 11 map
         
          
           ,bool>vis; 12 inline pair
           
            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
            
             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 else114 {115 cout<<"NO"<
             
              >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"<
              
               0.01)192 cout<
               
                <<" "<
                
                 <<" "<
                 
                  <