1————2————3————4————5————6
1->3 2
2->4 3
3->5 3
4->6 5
题目说 （u->v w）途中所有边 e1,e2,e3,...en∈E，满足任意|ex| >= w(ex∈E)，
上面图中 3->5 3 4->6 5,说明（|e(4->5)| >= 3 && |e(4->5)| >= 5） ==> |e(4->5)| >= 5。
通过这个想法，我们可以把边以（w）排序，大到小，先染色w大的，w小的不能去重新染色w大的，只能
染色未被染色的部分或者w相同的部分，例如（2->4）（3->5）w都是3,那么,如果某次（u->v w）无法染色，
说明就是"-1".
用了lca去优化（u->v）的寻路过程。
1 #include <iostream> 2 #include <algorithm> 3 #include <map> 4 #include <vector> 5 #include <cstdio> 6 using namespace std; 7 8 const int N = (int)5e3+10,INF = (int)1e6; 9 struct node{ 10 int to,nxt; 11 }e[N<<1]; 12 struct Info{ 13 int u,v,w; 14 bool friend operator<(const Info& a,const Info& b){ 15 return a.w > b.w; 16 } 17 }info[N]; 18 map<pair<int,int>, int > mp;//边 19 pair<int,int > pii; 20 vector<pair<int,int > > vii; 21 int n,m,u,v,w,tot,tim; 22 int head[N],dfn[N],fa[N]; 23 24 inline void add(int u,int v){ 25 e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; 26 e[tot].to = u; e[tot].nxt = head[v]; head[v] = tot++; 27 } 28 29 void dfs_dfn(int now,int pre){ 30 dfn[now] = ++tim; 31 for(int o = head[now]; ~o; o = e[o].nxt){ 32 if(e[o].to == pre) continue; 33 dfs_dfn(e[o].to,now); 34 } 35 } 36 37 void dfs_mp(int now,int pre){ 38 for(int o = head[now]; ~o; o = e[o].nxt){ 39 int to = e[o].to; 40 if(to == pre) continue; 41 fa[dfn[to]] = dfn[now]; 42 mp[make_pair(dfn[now],dfn[to])] = INF;//初始化边INF，把边的两点转化为dfn，总是以dnf小的在first位置 43 //输出答案的时候，通过dfn[u],dfn[v]去得到这条边 44 dfs_mp(e[o].to,now); 45 } 46 } 47 48 void show(){ 49 for(int i = 1; i <= n; ++i) 50 printf("u = %d dfn = %d\n",i,dfn[i]); 51 for(int i = 1; i <= m; ++i) cout << info[i].w << endl; 52 for(int i = 1; i <= n; ++i) 53 printf("u = %d fa = %d\n",i,fa[dfn[i]]); 54 } 55 56 bool lca(int u,int v,int w){ 57 int u_dfn = dfn[u],v_dfn = dfn[v],tmp_w; 58 bool ok = 0; 59 while(u_dfn != v_dfn){ 60 while(u_dfn > v_dfn){ 61 pii.first = fa[u_dfn]; pii.second = u_dfn; 62 tmp_w = mp[pii]; 63 if(tmp_w == INF || tmp_w == w){//未被染色，或者w相同 64 ok = 1; 65 mp[pii] = w; 66 } 67 u_dfn = pii.first; 68 } 69 while(u_dfn < v_dfn){ 70 pii.first = fa[v_dfn]; pii.second = v_dfn; 71 tmp_w = mp[pii]; 72 if(tmp_w == INF || tmp_w == w){ 73 ok = 1; 74 mp[pii] = w; 75 } 76 v_dfn = pii.first; 77 } 78 } 79 return ok; 80 } 81 82 void solve(){ 83 for(int i = 1; i <= n; ++i) head[i] = -1; tot = 0; 84 for(int i = 1; i <= n-1; ++i){ 85 scanf("%d%d",&u,&v); 86 vii.push_back(make_pair(u,v)); 87 add(u,v); 88 } 89 dfs_dfn(1,0);//初始化dfn序 90 fa[1] = 1; 91 dfs_mp(1,0);//初始化边长和fa[]数组 92 scanf("%d",&m); 93 for(int i = 1; i <= m; ++i){ 94 scanf("%d%d%d",&info[i].u,&info[i].v,&info[i].w); 95 } 96 97 sort(info+1,info+1+m);//边按W排序 98 for(int i = 1; i <= m; ++i){ 99 if(lca(info[i].u,info[i].v,info[i].w)) continue; 100 printf("-1\n"); return; 101 } 102 int l = vii.size(); 103 int dfn1,dfn2; 104 for(int i = 0; i < l; ++i){ 105 dfn1 = dfn[vii[i].first]; 106 dfn2 = dfn[vii[i].second]; 107 if(dfn1 > dfn2) swap(dfn1,dfn2); 108 pii.first = dfn1; pii.second = dfn2; 109 printf("%d ",mp[pii]); 110 }cout << endl; 111 } 112 113 int main(){ 114 115 scanf("%d",&n); 116 solve(); 117 118 return 0; 119 }