Dating

随便树上莫队搞一搞就好啦。

#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < ) a += mod;}
template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} const int B = ; int n, q, depth[N], f[N], pa[N][], gender[N];
int in[N], out[N], id[N], idx, op[N];
LL ans[N];
bool flag[N];
int cnt[][N]; vector<int> oo;
vector<int> G[N]; struct Qus {
int L, R, lca, id;
bool operator < (const Qus& rhs) const {
if(L / B == rhs.L / B) return R < rhs.R;
return L < rhs.L;
}
} qus[N]; int l, r; LL ret; inline void update(int x) {
ret += op[id[x]] * cnt[gender[id[x]] ^ ][f[id[x]]];
cnt[gender[id[x]]][f[id[x]]] += op[id[x]];
op[id[x]] = -op[id[x]];
} void dfs(int u, int fa) {
depth[u] = depth[fa] + ;
pa[u][] = fa;
for(int i = ; i < ; i++)
pa[u][i] = pa[pa[u][i - ]][i - ];
id[++idx] = u;
in[u] = idx;
for(auto& v : G[u]) {
if(v == fa) continue;
dfs(v, u);
}
id[++idx] = u;
out[u] = idx;
} int getLca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int i = ; ~i; i--)
if((depth[u] - depth[v]) >> i & )
u = pa[u][i];
if(u == v) return u;
for(int i = ; ~i; i--)
if(pa[u][i] != pa[v][i])
u = pa[u][i], v = pa[v][i];
return pa[u][];
} int main() {
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &gender[i]), op[i] = ;
for(int i = ; i <= n; i++) {
scanf("%d", &f[i]);
oo.push_back(f[i]);
}
for(int i = ; i < n; i++) {
int a, b; scanf("%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
sort(ALL(oo));
oo.erase(unique(ALL(oo)), oo.end());
for(int i = ; i <= n; i++)
f[i] = lower_bound(ALL(oo), f[i]) - oo.begin();
dfs(, );
scanf("%d", &q);
for(int i = ; i <= q; i++) {
int a, b, lca;
scanf("%d%d", &a, &b);
lca = getLca(a, b);
if(lca == a || lca == b) {
if(a == lca) qus[i] = Qus{in[a], in[b], a, i};
else qus[i] = Qus{in[b], in[a], b, i};
} else {
if(in[a] < in[b]) qus[i] = Qus{out[a], in[b], lca, i};
else qus[i] = Qus{out[b], in[a], lca, i};
}
}
l = , r = , ret = ;
sort(qus + , qus + + q);
for(int o = ; o <= q; o++) {
int L = qus[o].L, R = qus[o].R, lca = qus[o].lca, who = qus[o].id;
while(r < R) update(++r);
while(l > L) update(--l);
while(r > R) update(r--);
while(l < L) update(l++);
if(lca != id[L] && lca != id[R]) ans[who] = ret + cnt[gender[lca] ^ ][f[lca]];
else ans[who] = ret;
}
for(int i = ; i <= q; i++) printf("%lld\n", ans[i]);
return ;
} /*
*/

最新文章

  1. js-错误处理与调试,JSON
  2. 使用angular.js开发的一个简易todo demo
  3. json tree
  4. PHP开发环境设置
  5. 算法学习笔记(三) 最短路 Dijkstra 和 Floyd 算法
  6. js中如何在一个函数里面执行另一个函数
  7. 用FastDFS一步步搭建文件管理系统
  8. Free Pascal初次体验(有亮点哦)
  9. Electron的代码调试
  10. Java五道输出易错题解析(进来挑战下)
  11. mysql基础优化-explain的使用-mysql死锁
  12. &quot;==&quot;和 equals 方法究竟有什么区别?
  13. 用python计算圆周率Π
  14. Linux之备份(tar)/解压与压缩(gzip,bzip2,xz)【待完善】
  15. Python解析器
  16. 03: centos中配置使用svn
  17. sklearn使用小记GridSearchCV
  18. 【BZOJ3790】神奇项链 Manacher+贪心
  19. 关于Java的File类、字节流和字符流
  20. 【笔记】MySQL的基础学习

热门文章

  1. 如何从官网下载 Google Chrome 离线安装包
  2. 倍增\ tarjan求lca
  3. 「POJ2891」Strange Way to Express Integers【数学归纳法,扩展中国剩余定理】
  4. 「LibreOJ NOI Round #1」验题
  5. 一篇文章了解云安全领域的新宠CCSK
  6. RocketMQ_问题_启动控制台console报错,connect to &lt;null&gt; failed
  7. Hbase 元数据一致性检查(转)
  8. Docker:常用命令大全 [七]
  9. JavaScript 函数递归
  10. 拖动DIV