結果
| 問題 | No.3442 Good Vertex Connectivity |
| コンテスト | |
| ユーザー |
 沙耶花
|
| 提出日時 | 2026-02-06 22:44:57 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,053 bytes |
| 記録 | |
| コンパイル時間 | 5,971 ms |
| コンパイル使用メモリ | 298,760 KB |
| 実行使用メモリ | 37,500 KB |
| 最終ジャッジ日時 | 2026-02-06 22:46:18 |
| 合計ジャッジ時間 | 77,178 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 WA * 63 |
ソースコード
#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL
struct HLD{
vector<int> sz,parent,depth,root,pos;
vector<int> arr;
HLD(vector<vector<int>> &E){
if(E.size()==0)return;
sz.resize(E.size(),1);
parent.resize(E.size(),0);
depth.resize(E.size(),0);
root.resize(E.size(),0);
pos.resize(E.size(),0);
dfs(0,-1,E);
dfs2(0,-1,E,0);
}
void dfs(int now,int p,vector<vector<int>> &E){
parent[now] = p;
if(p==-1){
depth[now] = 0;
}
else{
depth[now] = depth[p]+1;
}
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
dfs(to,now,E);
sz[now] += sz[to];
}
}
void dfs2(int now,int p,vector<vector<int>> &E,int r){
pos[now] = arr.size();
arr.push_back(now);
root[now] = r;
int maxi = 0;
int ind = -1;
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p)continue;
if(maxi<sz[to]){
maxi = sz[to];
ind = to;
}
}
if(ind==-1)return;
dfs2(ind,now,E,r);
for(int i=0;i<E[now].size();i++){
int to = E[now][i];
if(to==p||to==ind)continue;
dfs2(to,now,E,to);
}
}
vector<pair<int,int>> query(int u,int v){
vector<pair<int,int>> ret;
int t = 0;
while(root[u]!=root[v]){
if(depth[root[u]] <= depth[root[v]]){
ret.insert(ret.begin()+t,{pos[root[v]], pos[v]});
v = parent[root[v]];
}
else{
ret.insert(ret.begin()+t,{pos[u],pos[root[u]]});
u = parent[root[u]];
t++;
}
}
ret.insert(ret.begin()+t,{pos[u],pos[v]});
return ret;
}
int lca(int u,int v){
for(;;v=parent[root[v]]){
if(pos[u]>pos[v])swap(u,v);
if(root[u]==root[v])return u;
}
}
int get_distance(int u,int v){
return depth[u] + depth[v] - 2 * depth[lca(u,v)];
}
};
int pos[200005],num[200005];
int sz[200005];
void dfs(int cv,int pv,vector<vector<int>> &E,int &cur){
num[cur] = cv;
pos[cv] = cur;
sz[cv] = 1;
cur++;
rep(i,E[cv].size()){
int to = E[cv][i];
if(to==pv)continue;
dfs(to,cv,E,cur);
sz[cv] += sz[to];
}
}
pair<int,int> get(fenwick_tree<int> &F,int l,int r){
int ok = l,ng = r;
while(ng-ok>1){
int mid = (ok+ng)/2;
if(F.sum(l,mid)==0)ok = mid;
else ng = mid;
}
int sum = F.sum(l,r);
int ok2 = r,ng2 = l;
while(ok2-ng2>1){
int mid = (ok2+ng2)/2;
if(F.sum(mid,r)==0)ok2 = mid;
else ng2 = mid;
}
return make_pair(ok,ok2-1);
}
vector<vector<int>> hoge;
HLD H(hoge);;
int op(int a,int b){
if(a==-1)return b;
if(b==-1)return a;
return H.lca(a,b);
}
int e(){
return -1;
}
int main(){
int n;
cin>>n;
vector<vector<int>> E(n);
rep(i,n-1){
int u,v;
cin>>u>>v;
u--,v--;
E[u].push_back(v);
E[v].push_back(u);
}
H = HLD(E);
int tt = 0;
dfs(0,-1,E,tt);
segtree<int,op,e> seg(n);
vector<int> c(n);
set<pair<int,int>> S;
rep(i,n){
cin>>c[i];
if(c[i])S.emplace(pos[i],i);
}
rep(i,n){
if(c[i]){
seg.set(pos[i],i);
}
}
fenwick_tree<long long> F(n);
fenwick_tree<int> Fc(n);
if(S.size()>=2){
auto it = S.begin();
auto it2 = S.begin();
it2++;
rep(i,S.size()-1){
F.add(it->first, H.get_distance(it->second,it2->second));
it++;
it2++;
}
}
rep(i,n){
Fc.add(pos[i],c[i]);
}
int Q;
cin>>Q;
rep(_,Q){
int t;
cin>>t;
if(t==1){
int x;
cin>>x;
x--;
if(c[x]==0){
Fc.add(pos[x],1);
seg.set(pos[x],x);
auto it = S.upper_bound(make_pair(pos[x],-1));
if(it!=S.begin()){
it--;
F.add(it->first, -F.sum(it->first,it->first+1));
F.add(it->first, H.get_distance(it->second, x));
}
it = S.lower_bound(make_pair(pos[x],-1));
if(it!=S.end()){
F.add(pos[x],H.get_distance(it->second,x));
}
S.emplace(pos[x],x);
}
else{
Fc.add(pos[x],-1);
seg.set(pos[x],-1);
F.add(pos[x],-F.sum(pos[x],pos[x]+1));
S.erase(make_pair(pos[x],x));
auto it = S.lower_bound(make_pair(pos[x],-1));
if(it!=S.begin()){
it--;
F.add(it->first,-F.sum(it->first,it->first+1));
auto it2 = it;
it2++;
if(it2!=S.end()){
F.add(it->first,H.get_distance(it->second,it2->second));
}
}
}
c[x] ^= 1;
}
else{
int x,y;
cin>>x>>y;
x--,y--;
if(H.lca(x,y)!=y||x==y){
if(Fc.sum(pos[y],pos[y]+sz[y])<=1){
cout<<Fc.sum(pos[y],pos[y]+sz[y])<<endl;
continue;
}
int yy = seg.prod(pos[y],pos[y]+sz[y]);
pair<int,int> t = get(Fc, pos[y], pos[y]+sz[y]);
long long ans = F.sum(t.first,t.second);
ans += H.get_distance(yy,num[t.first]);
ans += H.get_distance(yy,num[t.second]);
cout<<ans/2+1<<endl;
}
else{
int ll,rr;
{
int ok = pos[y],ng = pos[x];
while(ng-ok>1){
int mid = (ok+ng)/2;
if(H.lca(x,num[mid])==y)ok = mid;
else ng = mid;
}
rr = ok;
ok = pos[y]+sz[y], ng = pos[x];
while(ok-ng>1){
int mid = (ok+ng)/2;
if(H.lca(x,num[mid])==y)ok = mid;
else ng = mid;
}
ll = ok;
}
if(Fc.sum(pos[0],rr) + Fc.sum(ll,n)<=1){
cout<<Fc.sum(pos[0],rr) + Fc.sum(ll,n)<<endl;
continue;
}
long long ans = 0;
int yy= H.lca(seg.prod(pos[0],rr), seg.prod(ll,n));
if(Fc.sum(pos[0],rr)!=0){
pair<int,int> t = get(Fc,pos[0],rr);
ans += F.sum(t.first,t.second);
// cout<<ans<<endl;
if(Fc.sum(ll,n)==0){
ans += H.get_distance(yy,num[t.first]);
ans += H.get_distance(yy,num[t.second]);
}
else{
ans += H.get_distance(yy,num[t.first]);
//cout<<ans<<endl;
auto t2 = get(Fc,ll,n);
ans += H.get_distance(num[t2.first],num[t.second]);
t = t2;
// cout<<ans<<endl;
ans += F.sum(t.first,t.second);
ans += H.get_distance(yy,num[t.second]);
}
}
else{
pair<int,int> t = get(Fc,ll,n);
ans += F.sum(t.first,t.second);
ans += H.get_distance(yy,num[t.first]);
ans += H.get_distance(yy,num[t.second]);
}
cout<<ans/2+1<<endl;
}
}
}
return 0;
}