NOIP2018 - 一些板子

  1 #include<bits/stdc++.h>
  2 const int maxn = 30035;
  3 const int maxm = 60035;
  4 const int INF = 0x3f3f3f3f;
  5 
  6 struct node
  7 {
  8     int tot,fa,son,top;
  9 }a[maxn];
 10 int n,m;
 11 char opt[13];
 12 int f[maxn<<2][2];
 13 int chTot,chain[maxn],cnVal[maxn],d[maxn],dep[maxn];
 14 int edgeTot,head[maxn],nxt[maxm],edges[maxm];
 15 
 16 int read()
 17 {
 18     char ch = getchar();
 19     int num = 0;
 20     bool fl = 0;
 21     for (; !isdigit(ch); ch=getchar())
 22         if (ch==‘-‘) fl = 1;
 23     for (; isdigit(ch); ch=getchar())
 24         num = (num<<1)+(num<<3)+ch-48;
 25     if (fl) num = -num;
 26     return num;
 27 }
 28 void addedge(int u, int v)
 29 {
 30     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
 31     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
 32 }
 33 void pushup(int rt)
 34 {
 35     f[rt][1] = std::max(f[rt<<1][1], f[rt<<1|1][1]);
 36     f[rt][0] = f[rt<<1][0]+f[rt<<1|1][0];
 37 }
 38 void build(int rt, int l, int r)
 39 {
 40     f[rt][1] = -INF;
 41     if (l==r){
 42         f[rt][1] = f[rt][0] = cnVal[l];
 43         return;
 44     }
 45     int mid = (l+r)>>1;
 46     build(rt<<1, l, mid), build(rt<<1|1, mid+1, r);
 47     pushup(rt);
 48 }
 49 void dfs1(int x, int fa)
 50 {
 51     a[x].fa = fa, a[x].tot = 1;
 52     dep[x] = dep[fa]+1, a[x].son = -1;
 53     for (int i=head[x]; i!=-1; i=nxt[i])
 54     {
 55         int v = edges[i];
 56         if (v!=fa){
 57             dfs1(v, x);
 58             a[x].tot += a[v].tot;
 59             if (a[x].son==-1||a[v].tot > a[a[x].son].tot)
 60                 a[x].son = v;
 61         }
 62     }
 63 }
 64 void dfs2(int x, int top)
 65 {
 66     chain[x] = ++chTot, cnVal[chTot] = d[x], a[x].top = top;
 67     if (a[x].son==-1) return;
 68     dfs2(a[x].son, top);
 69     for (int i=head[x]; i!=-1; i=nxt[i])
 70     {
 71         int v = edges[i];
 72         if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v);
 73     }
 74 }
 75 void modify(int rt, int l, int r, int pos, int c)
 76 {
 77     if (l==r){
 78         f[rt][0] = f[rt][1] = c;
 79         return;
 80     }
 81     int mid = (l+r)>>1;
 82     if (pos <= mid) modify(rt<<1, l, mid, pos, c);
 83     else modify(rt<<1|1, mid+1, r, pos, c);
 84     pushup(rt);
 85 }
 86 int queryMx(int rt, int L, int R, int l, int r)
 87 {
 88     if (L <= l&&r <= R) return f[rt][1];
 89     int mid = (l+r)>>1, ret = -INF;
 90     if (L <= mid) ret = queryMx(rt<<1, L, R, l, mid);
 91     if (R > mid) ret = std::max(ret, queryMx(rt<<1|1, L, R, mid+1, r));
 92     return ret;
 93 }
 94 int querySm(int rt, int L, int R, int l, int r)
 95 {
 96     if (L <= l&&r <= R) return f[rt][0];
 97     int mid = (l+r)>>1, ret = 0;
 98     if (L <= mid) ret = querySm(rt<<1, L, R, l, mid); 
 99     if (R > mid) ret += querySm(rt<<1|1, L, R, mid+1, r);
100     return ret;
101 }
102 int queryChainMx(int x, int y)
103 {
104     int ret = -INF;
105     while (a[x].top!=a[y].top)
106     {
107         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);
108         ret = std::max(ret, queryMx(1, chain[a[y].top], chain[y], 1, n));
109         y = a[a[y].top].fa;
110     }
111     if (dep[x] > dep[y]) std::swap(x, y);
112     ret = std::max(ret, queryMx(1, chain[x], chain[y], 1, n));
113     return ret;
114 }
115 int queryChainSm(int x, int y)
116 {
117     int ret = 0;
118     while (a[x].top!=a[y].top)
119     {
120         if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);
121         ret += querySm(1, chain[a[y].top], chain[y], 1, n);
122         y = a[a[y].top].fa;
123     }
124     if (dep[x] > dep[y]) std::swap(x, y);
125     ret += querySm(1, chain[x], chain[y], 1, n);
126     return ret;
127 }
128 int main()
129 {
130     memset(head, -1, sizeof head);
131     n = read();
132     for (int i=1; i<n; i++) addedge(read(), read());
133     for (int i=1; i<=n; i++) d[i] = read();
134     dfs1(1, 0);
135     dfs2(1, 1);
136     build(1, 1, n);
137     m = read();
138     while (m--)
139     {
140         scanf("%s",opt);
141         int x = read(), y = read();
142         if (opt[0]==‘C‘) modify(1, 1, n, chain[x], y);
143         else if (opt[1]==‘M‘)
144             printf("%d\n",queryChainMx(x, y));
145         else printf("%d\n",queryChainSm(x, y));
146     }
147     return 0;
148 }