题目链接:http://codeforces.com/problemset/problem/1296/F

思路:

SRE实战,互联网时代守护先锋!让网站飞一会, 阿里云优惠促销大全。

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 }