首页 > 代码库 > 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;}
View Code

 

2566