\(\text{reflection}\)

初赛。

本来以为上午要愉快地周测,但是伟大的虎哥让我们在三楼接着练习
然后就目睹了一个万能头+return 0编译 1min30sec 的奇迹 Win7
打了第二类斯特林数 列
未果,寻病终。

下午开始考试
然后 锅锅f 又锅了
很奇妙地等了 20min 才能登陆
然后一个半小时写完了
就在那摆
改错了好几道题

然后考完了
想看一眼沈队 也没看到
但是后来就经常看到了

82.5pts.

复赛。

考前七天在宾馆隔离。
模拟赛成绩一次比一次差,到最后似乎是放弃了场上打正解的尝试
于是CSP时盯着傻瓜题的部分分就是拿
出场后发现除了我都切了

考试策略大概是每道题给一个小时,如果没有思路就赶紧打暴力滚蛋
然后四道题四个暴力
不知道能不能上 200pts
T1 感觉可以直接 sort 后取后 20 个 但是连大样例都过不去 40pts
T2 冲了 n + 4 个 st表后拿了 85pts,以为自己肯定想不出来这种nb题了就跳了
出场发现 T2 签到 wssb
T3 想到内向基环树森林后打了单次 \(O(n)\) 的sb拓扑排序 40pts
明明拿个set乱搞就能 60pts
正解思路不会 sum hash 从没见过
T4 打了暴力和 k = 1 的部分分 以为能有四十多分
但是出场一测代码发现nmd前向星没开双倍边
然后2e5的k=1都寄了 以后用vector(

最后看infoj的自测挂成了205pts
这次总体来说很寄,我是寄寄大王
希望 noip rp++
对了ioj自测里rk1是apj

赛后当天晚上在洗澡
10min 拿到了 350pts
行吧

白鸟过河滩好听的
link

\(\text{Solution}\)

好像这题解有点意识流?

T1 假期计划

小熊的地图上有 \(n\) 个点,其中编号为 \(1\) 的是它的家、编号为 \(2, 3, \ldots, n\) 的都是景点。部分点对之间有双向直达的公交线路。如果点 \(x\)\(z_1\)\(z_1\)\(z_2\)、……、\(z_{k – 1}\)\(z_k\)\(z_k\)\(y\) 之间均有直达的线路,那么我们称 \(x\)\(y\) 之间的行程可转车 \(k\) 次通达;特别地,如果点 \(x\)\(y\) 之间有直达的线路,则称可转车 \(0\) 次通达。

很快就要放假了,小熊计划从家出发去 \(4\)不同的景点游玩,完成 \(5\) 段行程后回家:家 \(\to\) 景点 A \(\to\) 景点 B \(\to\) 景点 C \(\to\) 景点 D \(\to\) 家且每段行程最多转车 \(k\) 次。转车时经过的点没有任何限制,既可以是家、也可以是景点,还可以重复经过相同的点。例如,在景点 A \(\to\) 景点 B 的这段行程中,转车时经过的点可以是家、也可以是景点 C,还可以是景点 D \(\to\) 家这段行程转车时经过的点。

假设每个景点都有一个分数,请帮小熊规划一个行程,使得小熊访问的四个不同景点的分数之和最大。

\(5 \le n \le 2500\)\(1 \le m \le 10000\)\(0 \le k \le 100\)

由于是 \(1\to a\to b\to c\to d\to 1\) 的无向图上环,考虑拆成 \(1\to a\to b + 1\to d\to c\) 的两条线路后拼合。
考虑枚举 \(b,c\),选择最优的 \(a,d\) 作为答案。由于 \(a \neq c, a\neq d\),需要对每个 \(b\) 维护前三大的答案。

首先在 \(O(nm)\) 的复杂度内处理任意两点间连通性,bfs 即可。

随后考虑 \(1\to a\to b\) 的路径。
枚举 \(b\),枚举每个点 \(a\)。若这两点可以拼合成路径,则将 \(a\) 插入 \(b\) 的答案集合中。
这部分的复杂度 \(O(n^2)\)

然后考虑枚举 \(b,c\),使用两个点的答案集合拼出答案。这时只需要保证四个点彼此不同,\(b\to c\) 可行即可。
这部分的复杂度 \(O(n^2)\),带 \(9\) 的常数。

于是我们在 \(O(nm + n^2)\) 的复杂度内得到答案。

当然你也可以记录 \(i\) 节点在拓展 \(1/2/3/4\) 次后前几长的路径,最后直接得到答案。时间复杂度相同。

code
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T> void get(T & x) {
	x = 0; char ch = getchar(); bool f = false;
	while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
	while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = s, i##_ = t + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = s, i##_ = t - 1; i > i##_; -- i)
const int N = 2500 + 10;
int n, m, k, a[N], t1, t2, gp[N][N], ans;
vector <int> g[N];

bool diff(const vector<int> a) {
    rep(i,0,a.size()-1) rep(j,i+1,a.size()-1) if (a[i] == a[j]) return false;
    return true;
} 

struct info {
    int self, pos[4], cnt;
    
    void insert(int p) {
        if (p == self) return;
        if (cnt < 3) pos[++cnt] = p, sort(pos+1, pos+1+cnt, [&](int x, int y){ return a[x] > a[y]; });
        else if (a[pos[3]] < a[p]) pos[3] = p, sort(pos+1, pos+1+cnt, [&](int x, int y){ return a[x] > a[y]; });
    }

    int operator + (const info & b) const {
        int ret = 0;
        rep(i,1,cnt) rep(j,1,b.cnt) {
            if (gp[self][b.self] and diff( {self, b.self, pos[i], b.pos[j]} )) {
                ret = max(ret, a[self] + a[b.self] + a[pos[i]] + a[b.pos[j]]);
            }
        } 
        return ret;
    }
} f[N];

int dis[N];
queue <int> que;
void bfs(int st) {
    rep(i,1,n) gp[st][i] = false, dis[i] = 1e9;
    gp[st][st] = true; dis[st] = 0; que.push(st);
    while (que.size()) {
        int u = que.front(); que.pop();
        if (dis[u] > k) continue; 
        for (int v : g[u]) if (dis[v] == 1e9) {
            dis[v] = dis[u] + 1; gp[st][v] = 1;
            que.push(v);
        }
    }
}

signed main() {
	get(n, m, k);
    rep(i,2,n) get(a[i]);
    rep(i,1,m) get(t1, t2), g[t1].push_back(t2), g[t2].push_back(t1);
    rep(i,1,n) bfs(i), f[i].self = i;
    rep(i,2,n) rep(j,2,n) if (i != j and gp[1][i] and gp[i][j]) f[j].insert(i);
	rep(i,2,n) rep(j,2,n) if (i != j) ans = max(ans, f[i] + f[j]);
    cout << ans << endl;
	return 0;
}


T2 策略游戏

有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\),在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\),满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。

游戏一共会进行 \(q\) 轮,在每一轮游戏中,会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\),满足 \(1 \le l_1 \le r_1 \le n\)\(1 \le l_2 \le r_2 \le m\)

游戏中,小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\),然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)

小 L 的目标是使得这个得分尽可能大,小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家,每次都会采用最优的策略。

请问:按照二人的最优策略,每轮游戏的得分分别是多少?

\(1 \le n, m, q \le {10}^5\)\(-{10}^9 \le A_i, B_i \le {10}^9\)

以为很nb 实际上是傻瓜题
我们开st表维护一个区间负数最值/区间正数最值
分类讨论模拟即可。

为什么 st表 比 线段树 慢一倍以上啊 明明query时少了个 log

code
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T> void get(T & x) {
	x = 0; char ch = getchar(); bool f = false;
	while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
	while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = s, i##_ = t + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = s, i##_ = t - 1; i > i##_; -- i)
const int N = 1e5 + 10; 
const int mx = 1e18;
int n, m, q, a[2][N], l1, r1, l2, r2;

int st[2][4][N][20]; // 0 : 正最大 1 : 负最大 2 : 正最小 3 : 负最小 
int lgv[N];

void init(const int & id, const int & n) {
    rep(i,1,n) {
        st[id][0][i][0] = (a[id][i] >= 0 ? a[id][i] : mx);
        st[id][1][i][0] = (a[id][i] <= 0 ? a[id][i] : mx);
        st[id][2][i][0] = (a[id][i] >= 0 ? a[id][i] : mx);
        st[id][3][i][0] = (a[id][i] <= 0 ? a[id][i] : mx);
    }
    rep(j,1,lgv[n]) for (int i = 1; i + (1 << j) - 1 <= n; ++ i) {
        rep(typ,0,1) {
            int x = st[id][typ][i][j-1], y = st[id][typ][i + (1 << j-1)][j - 1];
            if (x != mx and y != mx) st[id][typ][i][j] = max(x, y);
            else st[id][typ][i][j] = (x == mx ? y : x);
        } rep(typ,2,3) {
            int x = st[id][typ][i][j-1], y = st[id][typ][i + (1 << j-1)][j - 1];
            if (x != mx and y != mx) st[id][typ][i][j] = min(x, y);
            else st[id][typ][i][j] = (x == mx ? y : x);
        }
    }
}

int qry(int id, int typ, int l, int r) {
    int d = lgv[r - l + 1];
    if (typ < 2) {
        int x = st[id][typ][l][d], y = st[id][typ][r - (1 << d) + 1][d];
        if (x != mx and y != mx) return max(x, y);
        else return x == mx ? y : x;
    } else {
        int x = st[id][typ][l][d], y = st[id][typ][r - (1 << d) + 1][d];
        if (x != mx and y != mx) return min(x, y);
        else return x == mx ? y : x;
    }
}

struct ans {
    int max1, max2, min1, min2;
};

signed main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    get(n, m, q);
	rep(i,1,n) get(a[0][i]); rep(i,1,m) get(a[1][i]);
    rep(i,2,max(n, m)) lgv[i] = lgv[i >> 1] + 1;
    init(0, n); init(1, m);
    rep(i,1,q) {
        get(l1, r1, l2, r2);
        ans x = { qry(0, 0, l1, r1), qry(0, 1, l1, r1), qry(0, 2, l1, r1), qry(0, 3, l1, r1) }, 
            y = { qry(1, 0, l2, r2), qry(1, 1, l2, r2), qry(1, 2, l2, r2), qry(1, 3, l2, r2) };
		if(y.max2 == mx){
			if(x.max1 != mx) cout << 1ll * x.max1 * y.min1 << '\n';
			else cout << x.max2 * y.max1 << '\n';
		}
		else if(y.max1 == mx){
			if(x.max2 != mx) cout << x.min2 * y.max2 << '\n';
			else cout << x.min1 * y.min2 << '\n';
		}
		else {
			int res = -mx;
			if(x.max1 != mx) res = max(res, x.min1 * y.min2);
			if(x.max2 != mx) res = max(res, x.max2 * y.max1);
			cout << res << '\n';
		}
    }
	return 0;
}


T3 星战

给定一张 \(n\) 个点 \(m\) 条边的有向图。一条边 \(u\to v\) 属于 \(v\)

四种操作:

  1. 摧毁一条边,保证边存在且未被摧毁。
  2. 重建一条边,保证边存在且已被摧毁。
  3. 摧毁属于指定点的所有未被摧毁的边。
  4. 重建属于指定点的所有已被摧毁的边。

每次操作后询问当前未被摧毁的边能否形成内向基环树森林。

\(1 \le n,m,q \le 5 \times {10}^5\)

原题面真nm长

考虑为 YES 当且仅当每个点的出度为 \(1\)。这启发我们记录当前所有边的始点的信息。

考虑一个 sum hash,我们为每个点随机一个大权值,为 YES 只需所有边始点权值加和等于所有点权加和。

然而 2. 4. 操作仍然没法处理。发现 2. 4. 操作是批量改,而考虑 1. 3. 操作更改的边只有 \(O(q)\) 条,如果我们只修改被 1. 3. 操作更改的边就能做到 \(O(q\ f(q))\) 的复杂度。

对每个点开一个 set,其中存的值有两种可能:所有属于该点且被摧毁的边或属于该点且未被摧毁的边。
然后每次 2. 4. 操作暴力修改的复杂度就对了。

复杂度 \(O(q\log q)\)

code
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T> void get(T & x) {
	x = 0; char ch = getchar(); bool f = false;
	while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
	while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = s, i##_ = t + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = s, i##_ = t - 1; i > i##_; -- i)
const int N = 5e5 + 10, mod = 1e9 + 9e1; 
int n, m, q, typ, u, v, t1, t2, w1[N], w2[N], w1sum[N], w2sum[N], stat[N], sum1, sum2, hsh1, hsh2;
// stat[i] := i 对应 set 里保存的信息 为 1 则保存被删除的边的始点,为 0 则保存仍存在的边的始点 

set<int> st[N];
mt19937 rnd(random_device{}());

int add(int a, int b) { return (a + b) % mod; }

signed main() {
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    get(n, m);
    rep(i,1,n) {
        w1[i] = rnd() % 100000000, sum1 = add(sum1, w1[i]);
        w2[i] = rnd() % 100000000, sum2 = add(sum2, w2[i]);
        stat[i] = 1;
    }

    rep(i,1,m) {
        get(u, v);
        w1sum[v] = add(w1sum[v], w1[u]);
        w2sum[v] = add(w2sum[v], w2[u]);
        hsh1 = add(hsh1, w1[u]);
        hsh2 = add(hsh2, w2[u]);
    }

    get(q);
    while ( q-- ) {
        get(typ);
        if (typ == 1) {
            get(u, v);
            hsh1 = add(hsh1, mod - w1[u]), hsh2 = add(hsh2, mod - w2[u]);
            if (stat[v]) st[v].insert(u);
            else st[v].erase(u);
        } else if (typ == 2) {
            get(u); t1 = t2 = 0;
            for (int x : st[u]) {
                t1 = add(t1, w1[x]);
                t2 = add(t2, w2[x]);
            }
            if (stat[u] == 0) hsh1 = add(hsh1, - t1 + mod), hsh2 = add(hsh2, - t2 + mod);
            else hsh1 = add(hsh1, t1 - w1sum[u] + mod), hsh2 = add(hsh2, t2 - w2sum[u] + mod) % mod;
            st[u].clear();
            stat[u] = 0;
        } else if (typ == 3) {
            get(u, v);
            hsh1 = add(hsh1, w1[u]), hsh2 = add(hsh2, w2[u]);
            if (stat[v] == 0) st[v].insert(u);
            else st[v].erase(u);
        } else {
            get(u); t1 = t2 = 0;
            for (int x : st[u]) {
                t1 = add(t1, w1[x]);
                t2 = add(t2, w2[x]);
            }
            if (stat[u]) hsh1 = add(hsh1, t1), hsh2 = add(hsh2, t2);
            else hsh1 = add(hsh1, w1sum[u] - t1 + mod), hsh2 = add(hsh2, w2sum[u] - t2 + mod) % mod;
            st[u].clear();
            stat[u] = 1;
        }
        puts((hsh1 == sum1 and hsh2 == sum2) ? "YES" : "NO");
    }
	return 0;
}


T4 数据传输

小 C 正在设计计算机网络中的路由系统。
测试用的网络总共有 \(n\) 台主机,依次编号为 \(1 \sim n\)。这 \(n\) 台主机之间由 \(n – 1\) 根网线连接,第 \(i\) 条网线连接个主机 \(a_i\)\(b_i\)。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率,主机 \(a\) 能够直接将信息传输给主机 \(b\) 当且仅当两个主机在可以通过不超过 \(k\) 根网线直接或者间接的相连。

在计算机网络中,数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 \(a\) 传输到主机 \(b\)\(a \neq b\)),则其会选择出若干台用于传输的主机 \(c_1 = a, c_2, \ldots, c_{m – 1}, c_m = b\),并按照如下规则转发:对于所有的 \(1 \le i < m\),主机 \(c_i\) 将信息直接发送给 \(c_{i + 1}\)

每台主机处理信息都需要一定的时间,第 \(i\) 台主机处理信息需要 \(v_i\) 单位的时间。数据在网络中的传输非常迅速,因此传输的时间可以忽略不计。据此,上述传输过程花费的时间为 \(\sum_{i = 1}^{m} v_{c_i}\)

现在总共有 \(q\) 次数据发送请求,第 \(i\) 次请求会从主机 \(s_i\) 发送数据到主机 \(t_i\)。小 C 想要知道,对于每一次请求至少需要花费多少单位时间才能完成传输。

\(1 \le n, q \le 2 \times {10}^5\)\(1 \le k \le 3\)\(1 \le a_i, b_i \le n\)\(1 \le s_i, t_i \le n\)\(s_i \ne t_i\)

场上看到 \(1\le k \le 3\) 感觉是个 sb 数据点分治题
最后发现不是
但是部分分肯定得分治(

k=1 打个树上前缀和就行,k=2 我们发现跳出原链肯定不优因此剖后矩阵乘维护 dp 数组即可。
然后是 k=3.
我们发现 k=3 的转移点都在某个点周围长为 1 的范围内,因此考虑对每个点扫一遍找到它的转移点即可类似 k=2 的情况转移了。

然后剖。剖完维护一个向上的矩乘和向下的矩乘,顺着链扫出需要的矩阵,再把第二段 reverse 一下就能得到需要的 \(O(\log n)\) 个矩阵。顺着乘起来就行了。

时间复杂度 \(O(n \log^2 n)\),带个 \(9\) 的常数。
当然可以维护每条链从链顶到任意链上位置的矩阵,然后复杂度剪掉一个 \(\log\)。但是常数大得多,时空复杂度都不如两个 \(\log\) 的做法。可能是我写挂了?
这里放两个 \(\log\) 的做法。

code
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T> void get(T & x) {
	x = 0; char ch = getchar(); bool f = false;
	while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
	while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = s, i##_ = t + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = s, i##_ = t - 1; i > i##_; -- i)
const int N = 2e5 + 10; 
int n, q, k, t1, t2, valk[N];
int dep[N], fa[N], siz[N], son[N], dfn[N], idfn[N], stp, top[N];
vector <int> g[N];

struct mat {
    int a[3][3], n, m;

    mat(int _n, int _m) : n(_n), m(_m) { memset(a, 0x3f, sizeof a); }
    mat(int _n = 0) : n(_n), m(_n) { memset(a, 0x3f, sizeof a); rep(i,0,n-1) a[i][i] = 0; }
    int* operator[] (const int & p) { return a[p]; }
    const int* operator[] (const int & p) const { return a[p]; }

    mat operator* (const mat & b) const {
        mat ret(n, b.m); 
        rep(i,0,n-1) rep(j,0,b.m-1) rep(k,0,m-1) {
            ret[i][j] = min(ret[i][j], a[i][k] + b[k][j]);
        } return ret;
    }
};

struct SegmentBeats {
    mat seg[N << 2];
    #define ls (p << 1)
    #define rs (p << 1 | 1)

    void upd(int p, int l, int r, int pos, mat val) {
        if (l == r) { seg[p] = val; return; }
        int mid = l + r >> 1;
        if (pos <= mid) upd(ls, l, mid, pos, val);
        else upd(rs, mid+1, r, pos, val);
        seg[p] = seg[ls] * seg[rs];
    }

    mat qry(int p, int l, int r, int L, int R) {
        if (L > R) return mat(k);
        if (L <= l and r <= R) return seg[p];
        int mid = l + r >> 1;
        if (R <= mid) return qry(ls, l, mid, L, R);
        else if (mid < L) return qry(rs, mid+1, r, L, R);
        else return qry(ls, l, mid, L, R) * qry(rs, mid+1, r, L, R);
    }

    #undef ls
    #undef rs
} tr1, tr2;
 
void find_hc(int u, int f) {
    dep[u] = dep[f] + 1, fa[u] = f; siz[u] = 1;
    for (int v : g[u]) if (v != f) {
        find_hc(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void con_hc(int u, int ctop) {
    dfn[u] = ++stp, idfn[stp] = u; top[u] = ctop;
    if (son[u]) con_hc(son[u], ctop);
    for (int v : g[u]) if (v != fa[u] and v != son[u]) {
        con_hc(v, v);
    }
}

int find(int u) { 
    int ans = 2e9;
    for (int v : g[u]) ans = min(ans, valk[v]);
    return ans;
}

mat getv(int u) {
    mat ret(k, k);
    rep(i,0,k-1) ret[i][0] = valk[u];
    rep(i,1,k-1) ret[i-1][i] = 0;
    if (k == 3) ret[1][1] = find(u);
    return ret;
}

void upd(int pos, mat val) {
    tr1.upd(1, 1, n, dfn[pos], val);
    tr2.upd(1, 1, n, n - dfn[pos] + 1, val);
}

int query(int s, int t) {
    int S = s;
    static vector<mat> a, b; a.clear(), b.clear();
    bool ck = true;
    while (top[s] != top[t]) {
        if (dep[top[s]] > dep[top[t]]) {
            if (ck) a.push_back(tr2.qry(1, 1, n, n - dfn[s] + 2, n - dfn[top[s]] + 1)), ck = false;
            else    a.push_back(tr2.qry(1, 1, n, n - dfn[s] + 1, n - dfn[top[s]] + 1));
            s = fa[top[s]];
        } else {
            b.push_back(tr1.qry(1, 1, n, dfn[top[t]], dfn[t]));
            t = fa[top[t]];
        }
    } if (dfn[s] >= dfn[t]) {
        if (ck) a.push_back(tr2.qry(1, 1, n, n - dfn[s] + 2, n - dfn[t] + 1)), ck = false;
        else    a.push_back(tr2.qry(1, 1, n, n - dfn[s] + 1, n - dfn[t] + 1));
    } else {
        if (ck) b.push_back(tr1.qry(1, 1, n, dfn[s] + 1, dfn[t])), ck = false;
        else    b.push_back(tr1.qry(1, 1, n, dfn[s], dfn[t]));
    } 
    reverse(b.begin(), b.end());
    mat w(1, k);
    w[0][0] = valk[S];
    for (mat tmp : a) w = w * tmp;
    for (mat tmp : b) w = w * tmp;
    return w[0][0];
}

signed main() {
    get(n, q, k);
    rep(i,1,n) get(valk[i]); 
    rep(i,2,n) get(t1, t2), g[t1].push_back(t2), g[t2].push_back(t1);
    find_hc(1, 0); con_hc(1, 1);
    rep(i,1,n) upd(i, getv(i));
    while ( q-- ) {
        get(t1, t2);
        cout << query(t1, t2) << '\n';
    }

	return 0;
}

原文地址:http://www.cnblogs.com/joke3579/p/csp-s-jile.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性