@[STARS_czy](/user/656765) 你这个把输出函数和输入函数一改就行了
by Doors_Cross @ 2024-03-18 16:08:42
@[Doors_Cross](/user/1157659) 哦哦哦C语言有 `for auto` 还有 `vector`
by chat_jinxuan @ 2024-03-18 16:11:20
@[Doors_Cross](/user/1157659) @[chat_jinxuan](/user/726525) 好了。原来A的程序现在 T 了，能不能帮忙看看。
```cpp
#include <stdio.h>
#include <string.h>
#define int long long
typedef long long ll;
const int mod = 998244353;
int T, n, idtt, eu[400010], ev[400010], ew[400010], dep[400010], sz[400010], fa[400010];
int hs[400010], lt[400010], id[400010], tmp[400010], val[400010], mx[400010];
int ett,head[400010],nxt[400010],to[400010],hv[400010];
void inserte(int u,int v,int w){
to[++ett]=v;
nxt[ett]=head[u];
hv[ett]=w;
head[u]=ett;
}
void dfs1(int u){
sz[u] = 1;
for (int i = head[u]; i; i=nxt[i]) {
int v = to[i];
int w = hv[i];
if (v != fa[u]) {
fa[v] = u;
val[v] = w;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (sz[v] > sz[hs[u]]) hs[u] = v;
}
}
}
void dfs2(int u){
if (!lt[u]) lt[u] = u;
lt[hs[u]] = lt[u];
tmp[id[u] = ++idtt] = val[u];
if (hs[u]) dfs2(hs[u]);
for (int i = head[u]; i; i=nxt[i]) {
int v = to[i];
if (v != fa[u] && v != hs[u]) dfs2(v);
}
}
void pushup(int id) {
mx[id] = mx[id << 1] > mx[id << 1 | 1] ? mx[id << 1] : mx[id << 1 | 1];
}
void build(int id, int l, int r, int *tmp) {
if (l == r) {
mx[id] = tmp[l];
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, tmp);
build(id << 1 | 1, mid + 1, r, tmp);
pushup(id);
}
void change(int id, int l, int r, int k, int x) {
if (l == r) {
mx[id] = x;
return;
}
int mid = (l + r) >> 1;
if (k <= mid) change(id << 1, l, mid, k, x);
else change(id << 1 | 1, mid + 1, r, k, x);
pushup(id);
}
int query(int id, int l, int r, int lq, int rq) {
if (lq <= l && r <= rq) return mx[id];
int mid = (l + r) >> 1, ls = 0,rs=0;
if (lq <= mid) ls = query(id << 1, l, mid, lq, rq);
if (rq > mid) rs = query(id << 1 | 1, mid + 1, r, lq, rq);
return ls>rs?ls:rs;
}
signed main() {
int i, o;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
idtt = 0,ett=0;
for (i = 1; i <= n - 1; ++i) {
scanf("%lld %lld %lld", &eu[i], &ev[i], &ew[i]);
inserte(eu[i],ev[i],ew[i]),inserte(ev[i],eu[i],ew[i]);
}
dfs1(1);
dfs2(1);
build(1, 1, n, tmp);
for (o = 1; o <= 3e5; ++o) {
int u, v, k, w, ans = 0;
char opt[10];
scanf("%s", opt);
if (strcmp(opt, "DONE") == 0) break;
if (strcmp(opt, "CHANGE") == 0) {
scanf("%lld %lld", &k, &w);
if (dep[eu[k]] < dep[ev[k]]) {
int temp = eu[k];
eu[k] = ev[k];
ev[k] = temp;
}
change(1, 1, n, id[eu[k]], w);
continue;
}
scanf("%lld %lld", &u, &v);
for (; lt[u] != lt[v]; u = fa[lt[u]]) {
if (dep[lt[u]] < dep[lt[v]]) {
int temp = u;
u = v;
v = temp;
}
ans = ans > query(1, 1, n, id[lt[u]], id[u]) ? ans : query(1, 1, n, id[lt[u]], id[u]);
}
if (id[u] > id[v]) {
int temp = u;
u = v;
v = temp;
}
if (u != v) ans = ans > query(1, 1, n, id[u] + 1, id[v]) ? ans : query(1, 1, n, id[u] + 1, id[v]);
printf("%lld\n", ans);
}
memset(hs, 0, sizeof(hs));
memset(lt, 0, sizeof(lt));
memset(nxt, 0, sizeof(nxt));
memset(to, 0, sizeof(to));
memset(hv, 0, sizeof(hv));
}
return 0;
}
by STARS_czy @ 2024-03-18 16:22:11
你不配
by danwei1 @ 2024-03-18 16:23:12
@[STARS_czy](/user/656765) 这就A了
by chat_jinxuan @ 2024-03-18 16:25:04
@[danwei1](/user/737864) ???
by STARS_czy @ 2024-03-18 16:27:04
A 了，感谢。
by STARS_czy @ 2024-03-18 16:34:58