首页 > 代码库 > 2566
2566
#include<cstdio>#include<cstring>#include<set>#include<algorithm>#include<vector>using namespace std;const int MAX_SIZE = 12000;const int INF = 0x3f3f3f3f;struct Node{ int l, r; Node *left, *right; int minn, tag;};Node tree[MAX_SIZE * 2 + 10]; int tn;inline void update(Node* cur, int v){ if(cur -> tag > v){ cur -> tag = v; cur -> minn = min(cur -> minn, v); }}inline void pushDown(Node* cur){ if(cur -> tag != INF){ if(cur -> l != cur -> r){ update(cur -> left, cur -> tag); update(cur -> right, cur -> tag); } cur -> tag = INF; }}Node* build(int l, int r){ Node* cur = tree + (tn ++); cur -> l = l; cur -> r = r; cur -> minn = cur -> tag = INF; if(l != r){ int mid = (l + r) >> 1; cur -> left = build(l, mid); cur -> right = build(mid + 1, r); } return cur;}Node* sroot;struct O{ int id, co;};vector<int> event[MAX_SIZE + 10];multiset<int> s[MAX_SIZE * 2 + 10];int val[MAX_SIZE * 2 + 10], vn;int data[MAX_SIZE + 10], n;int nodes[MAX_SIZE + 10], nxt[MAX_SIZE * 2 + 10], to[MAX_SIZE * 2 + 10], en;int len[MAX_SIZE * 2 + 10];int m;bool vis[MAX_SIZE + 10];int root, minn, tot, size[MAX_SIZE + 10];O cg[MAX_SIZE + 10];int dist[MAX_SIZE + 10], clist[MAX_SIZE + 10], cn;int cco[MAX_SIZE + 10];int pre[MAX_SIZE * 2 + 10], tVal[MAX_SIZE * 2 + 10];inline void addEdge(int f, int t, int w){ ++ en; to[en] = t; len[en] = w; nxt[en] = nodes[f]; nodes[f] = en;}void dfs(int cur, int fa){ size[cur] = 1; for(int e = nodes[cur]; e; e = nxt[e]){ if(to[e] == fa || vis[to[e]]) continue; dfs(to[e], cur); size[cur] += size[to[e]]; }}void findRoot(int cur, int fa){ int maxn = tot - size[cur]; for(int e = nodes[cur]; e; e = nxt[e]){ if(to[e] == fa || vis[to[e]]) continue; if(size[to[e]] > maxn) maxn = size[to[e]]; findRoot(to[e], cur); } if(maxn < minn){ minn = maxn; root = cur; }}void dfsDist(int cur, int fa){ int si = (int)event[cur].size(); for(int i = 0; i < si; i ++) clist[++ cn] = event[cur][i]; cco[cur] = data[cur]; int p = lower_bound(val, val + vn, data[cur]) - val; s[p].insert(dist[cur]); if((int)s[p].size() > 1){ set<int>::iterator it = s[p].begin(); int d = *it; ++ it; d += *it; if(tVal[p] > d) tVal[p] = d; } for(int e = nodes[cur]; e; e = nxt[e]){ if(to[e] == fa || vis[to[e]]) continue; dist[to[e]] = dist[cur] + len[e]; dfsDist(to[e], cur); }}void change(Node* cur, int l, int r, int v){ if(cur -> l == l && cur -> r == r){ update(cur, v); return; } pushDown(cur); int mid = (cur -> l + cur -> r) >> 1; if(r <= mid) change(cur -> left, l, r, v); else if(l > mid) change(cur -> right, l, r, v); else{ change(cur -> left, l, mid, v); change(cur -> right, mid + 1, r, v); } cur -> minn = min(cur -> left -> minn, cur -> right -> minn);}void clear(int cur, int fa){ int p = lower_bound(val, val + vn, cco[cur]) - val; s[p].clear(); p = lower_bound(val, val + vn, data[cur]) - val; change(sroot, pre[p], m, tVal[p]); pre[p] = 0; tVal[p] = INF; for(int e = nodes[cur]; e; e = nxt[e]){ if(to[e] == fa || vis[to[e]]) continue; clear(to[e], cur); }}void work(int cur){ dfs(cur, 0); tot = size[cur]; minn = INF; findRoot(cur, 0); cur = root; dist[cur] = 0; cn = 0; dfsDist(cur, 0); sort(clist + 1, clist + cn + 1); for(int i = 1; i <= cn; i ++){ int t = clist[i]; int p; p = lower_bound(val, val + vn, cco[cg[t].id]) - val; s[p].erase(s[p].find(dist[cg[t].id])); int d; if((int)s[p].size() > 1){ set<int>::iterator it = s[p].begin(); d = *it; ++ it; d += *it; } else d = INF; if(pre[p] != t){ change(sroot, pre[p], t - 1, tVal[p]); pre[p] = t; tVal[p] = d; } else tVal[p] = min(tVal[p], d); cco[cg[t].id] = cg[t].co; p = lower_bound(val, val + vn, cco[cg[t].id]) - val; s[p].insert(dist[cg[t].id]); if((int)s[p].size() > 1){ set<int>::iterator it = s[p].begin(); d = *it; ++ it; d += *it; } else d = INF; if(pre[p] != t){ change(sroot, pre[p], t - 1, tVal[p]); pre[p] = t; tVal[p] = d; } else tVal[p] = min(tVal[p], d); } // s[0].clear(); for(int i = 1; i <= cn; i ++){ int t = clist[i]; int p = lower_bound(val, val + vn, cg[t].co) - val; change(sroot, pre[p], m, tVal[p]); pre[p] = 0; tVal[p] = INF; } clear(cur, 0); vis[cur] = true; for(int e = nodes[cur]; e; e = nxt[e]){ if(!vis[to[e]]) work(to[e]); }}void print(Node* cur){ if(cur -> l == cur -> r){ if(cur -> minn == INF) printf("-1\n"); else printf("%d\n", cur -> minn); return; } pushDown(cur); print(cur -> left); print(cur -> right);}int main(){#ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#endif scanf("%d", &n); for(int i = 1; i <= n; i ++){ scanf("%d", data + i); val[vn ++] = data[i]; } for(int i = 1; i < n; i ++){ int a, b, w; scanf("%d%d%d", &a, &b, &w); addEdge(a, b, w); addEdge(b, a, w); } scanf("%d", &m); for(int i = 1; i <= m; i ++){ scanf("%d%d", &cg[i].id, &cg[i].co); event[cg[i].id].push_back(i); val[vn ++] = cg[i].co; } sort(val, val + vn); vn = unique(val, val + vn) - val; sroot = build(0, m); memset(tVal, INF, sizeof(tVal)); work(1); for(int i = 0; i < vn; i ++) s[0].insert(INF); memset(pre, INF, sizeof(pre)); print(sroot);// printf("%d\n", pre[2]); return 0;}
2566
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。