#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=400005,B=1; int n,m,q; int dep[N],fol[N],ffa[N],tot; int dfn[N],DFN; int st[N][20]; poly G[N],gf[N],key[N]; int col[N]; int vs[N]; int ins[N],del[N]; pa E[N]; int d[N]; map<pa,int>Mp; int op[N],a[N],b[N],c[N]; int lstvis[N],upd[N]; int siz[N]; inline int chkmin(int x,int y) { if (dep[x]<dep[y]) return x; return y; } inline int lca(int x,int y) { if (x==y) return x; if (dfn[x]>dfn[y]) swap(x,y); x=dfn[x]+1,y=dfn[y]; int t=__lg(y-x+1); return chkmin(st[x][t],st[y-(1<<t)+1][t]); } inline int dis(int x,int y) { return dep[x]+dep[y]-2*dep[lca(x,y)]; } void dfs(int k,int fa,int tim) { fol[k]=tot; ffa[k]=fa; dfn[k]=++DFN; st[DFN][0]=fa; siz[k]=1; for (auto U:G[k]) { if (!(ins[U]<=tim&&tim<del[U])||(E[U].fi^E[U].se^k)==fa) continue; int u=E[U].fi^E[U].se^k; dep[u]=dep[k]+d[U]; dfs(u,k,tim); siz[k]+=siz[u]; } } void color(int k,int fa,int ds,int cc,int tim) { if (vs[k]) return; col[k]=cc; for (auto U:G[k]) { if (!(ins[U]<=tim&&tim<del[U])) continue; int u=E[U].fi^E[U].se^k; if (u==fa) continue; if (ds>=d[U]) color(u,k,ds-d[U],cc,tim); } } void BellaKira() { cin>>n>>m>>q; for (int i=1;i<=m;i++) { cin>>E[i].fi>>E[i].se>>d[i]; if (E[i].fi>E[i].se) swap(E[i].fi,E[i].se); auto [x,y]=E[i]; G[x].push_back(i); G[y].push_back(i); Mp[E[i]]=i; ins[i]=0; del[i]=q+1; } for (int i=1;i<=q;i++) { cin>>op[i]; if (op[i]==1) { cin>>a[i]>>b[i]>>c[i]; if (a[i]>b[i]) swap(a[i],b[i]); ++m; E[m]=mp(a[i],b[i]); d[m]=c[i]; G[a[i]].push_back(m); G[b[i]].push_back(m); Mp[E[m]]=m; ins[m]=i; del[m]=q+1; a[i]=m; } else if (op[i]==2) { cin>>a[i]>>b[i]; if (a[i]>b[i]) swap(a[i],b[i]); a[i]=Mp[mp(a[i],b[i])]; del[a[i]]=i; } else if (op[i]==3) { cin>>a[i]>>b[i]>>c[i]; color(a[i],0,b[i],c[i],i); } else cin>>a[i],cout<<col[a[i]]<<'\n'; } } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define sz(x) (int)((x).size()) #define int ll //#define N using namespace std; const int N=400005,B=1; int n,m,q; int dep[N],fol[N],ffa[N],tot; int dfn[N],DFN; int st[N][20]; poly G[N],gf[N],key[N]; int col[N]; int vs[N]; int ins[N],del[N]; pa E[N]; int d[N]; map<pa,int>Mp; int op[N],a[N],b[N],c[N]; int lstvis[N],upd[N]; int siz[N]; inline int chkmin(int x,int y) { if (dep[x]<dep[y]) return x; return y; } inline int lca(int x,int y) { if (x==y) return x; if (dfn[x]>dfn[y]) swap(x,y); x=dfn[x]+1,y=dfn[y]; int t=__lg(y-x+1); return chkmin(st[x][t],st[y-(1<<t)+1][t]); } inline int dis(int x,int y) { return dep[x]+dep[y]-2*dep[lca(x,y)]; } void dfs(int k,int fa,int tim) { fol[k]=tot; ffa[k]=fa; dfn[k]=++DFN; st[DFN][0]=fa; siz[k]=1; for (auto U:G[k]) { if (!(ins[U]<=tim&&tim<del[U])||(E[U].fi^E[U].se^k)==fa) continue; int u=E[U].fi^E[U].se^k; dep[u]=dep[k]+d[U]; dfs(u,k,tim); siz[k]+=siz[u]; } } void color(int k,int fa,int ds,int cc,int tim) { if (vs[k]) return; col[k]=cc; for (auto U:G[k]) { if (!(ins[U]<=tim&&tim<del[U])) continue; int u=E[U].fi^E[U].se^k; if (u==fa) continue; if (ds>=d[U]) color(u,k,ds-d[U],cc,tim); } } void BellaKira() { cin>>n>>m>>q; for (int i=1;i<=m;i++) { cin>>E[i].fi>>E[i].se>>d[i]; if (E[i].fi>E[i].se) swap(E[i].fi,E[i].se); auto [x,y]=E[i]; G[x].push_back(i); G[y].push_back(i); Mp[E[i]]=i; ins[i]=0; del[i]=q+1; } for (int i=1;i<=q;i++) { cin>>op[i]; if (op[i]==1) { cin>>a[i]>>b[i]>>c[i]; if (a[i]>b[i]) swap(a[i],b[i]); ++m; E[m]=mp(a[i],b[i]); d[m]=c[i]; G[a[i]].push_back(m); G[b[i]].push_back(m); Mp[E[m]]=m; ins[m]=i; del[m]=q+1; a[i]=m; } else if (op[i]==2) { cin>>a[i]>>b[i]; if (a[i]>b[i]) swap(a[i],b[i]); a[i]=Mp[mp(a[i],b[i])]; del[a[i]]=i; } else if (op[i]==3) { cin>>a[i]>>b[i]>>c[i]; color(a[i],0,b[i],c[i],i); } else cin>>a[i],cout<<col[a[i]]<<'\n'; } } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } |