LWDB

<cstdio> #include <cstring> #include <vector> #include <algorithm> #define p E[i].x #define N 100010 #define M 7000010 #define l(x) ch[x][0] #define r(x) ch[x][1] #define MP(x, y) make_pair(x, y) #define LL long long using namespace std; typedef pair<int,int> PII; struct edge { int x, to, v; }E[N<<1]; int totE, totn, n, m, hev, lef_now; int g[N], h[N], de[N], siz[N], root[N], fa[N][21], col[N], d[N]; int ch[M][2], setv[M]; vector<PII> nod[N], id[N]; vector<int> hevs[N]; int dis[N][21]; bool v[N]; void addedge(int x, int y, int v) { E[++totE] = (edge){y, g[x], v}; g[x] = totE; } int build(int l, int r) { int x = ++totn; setv[x] = 0; if(l == r) return x; int mid = (l+r)>>1; l(x) = build(l, mid); r(x) = build(mid+1, r); return x; } void push(int x) { if(!setv[x]) return; setv[l(x)] = setv[x]; setv[r(x)] = setv[x]; setv[x] = 0; } int ask(int x, int l, int r, int qx) { if(l<r) push(x); if(l == r) return setv[x]; int mid = (l+r)>>1; if(qx <= mid) return ask(l(x), l, mid, qx); else return ask(r(x), mid+1, r, qx); } void change(int x, int l, int r, int ql, int qr, int qv) { if(l<r) push(x); if(ql<=l && r<=qr) { setv[x] = qv; return; } int mid=(l+r)>>1; if(ql <= mid) change(l(x),l,mid,ql,qr,qv); if(mid < qr) change(r(x),mid+1,r,ql,qr,qv); } int dist(int x, int y) { if(de[x] < de[y]) swap(x, y); int ans = 0; for(int i = 20;~i;i--) if(de[fa[x][i]] >= de[y]) ans += dis[x][i], x = fa[x][i]; if(x == y) return ans; for(int i = 20;~i;i--) if(fa[x][i] != fa[y][i]) { ans += dis[x][i]; x = fa[x][i]; ans += dis[y][i]; y = fa[y][i]; } return ans+dis[x][0]+dis[y][0]; } void dfs1(int x, int tmp) { siz[x] = 1; h[x] = 0; for(int i = g[x];i;i = E[i].to) if(!v[p] && p != tmp) { dfs1(p, x); h[x] = max(h[x], siz[p]); siz[x] += siz[p]; } h[x] = max(h[x], lef_now - siz[x]); if(!hev || h[x] < h[hev]) hev = x; } void dfs(int x) { for(int i = g[x];i;i = E[i].to) if(p != fa[x][0]) { fa[p][0] = x; dis[p][0] = E[i].v; de[p] = de[x] + 1; dfs(p); } } void dfs2(int x, int tmp, int now) { nod[now].push_back(MP(d[x], x)); for(int i = g[x];i;i = E[i].to) if(!v[p] && p != tmp) { d[p] = d[x] + E[i].v; dfs2(p, x, now); } } void solve(int x) { v[x] = 1; d[x] = 0; dfs2(x, x, x); sort(nod[x].begin(), nod[x].end()); for(int i = 0;i < (int)nod[x].size();i++) { id[x].push_back( MP(nod[x][i].second, i) ); hevs[nod[x][i].second].push_back(x); } sort(id[x].begin(), id[x].end()); root[x] = build(0, nod[x].size()-1); for(int i = g[x];i;i = E[i].to) if(!v[p]) { hev = 0; lef_now = siz[p]; dfs1(p, x); solve(hev); } } int find(int x,int len) { int l=0,r=nod[x].size()-1; while(r-l>4) { int mid = (l+r)>>1; if(nod[x][mid].first <= len) l=mid; else r=mid; } for(int i=r;i>=l;i--) if(nod[x][i].first <= len) return i; return -1; } void com_change(int x, int len, int v) { for(int i = 0;i < (int)hevs[x].size();i++) { int tmp = hevs[x][i]; int t = find(tmp, len - dist(x, tmp)); if(t == -1) continue; change(root[tmp], 0, id[tmp].size()-1, 0, t, v); } } int com_ask(int x) { int ans = 0; for(int i = 0;i < (int)hevs[x].size();i++) { int tmp = hevs[x][i]; int t = (*lower_bound(id[tmp].begin(), id[tmp].end(), MP(x, -1))).second; ans = max(ans, ask(root[tmp], 0, id[tmp].size()-1, t)); } return col[ans]; } int main() { scanf("%d", &n); for(int i = 1, x, y, v;i < n;i++) { scanf("%d %d %d", &x, &y, &v); addedge(x, y, v); addedge(y, x, v); } de[1]=1; dfs(1); for(int j = 1;j <= 20;j++) { for(int i = 1;i <= n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; dis[i][j] = dis[fa[i][j-1]][j-1] + dis[i][j-1]; } } totn = 0; hev = 0; lef_now = n; dfs1(1, 1); solve(hev); scanf("%d", &m); int x,cmd,len,tot=0; while(m--) { scanf("%d%d",&cmd,&x); if(cmd==1) { scanf("%d%d",&len,&col[++tot]); com_change(x,len,tot); } else printf("%d\n",com_ask(x)); } return 0; } View Code

 

LWDB

标签：分享   efi   时间   root   algo   main   问题   颜色   i++