\[だから妄想感傷代償連盟 \]\[愛を懐いて理想を叫んだ \]\[行き場のない愚者のメロディー \]\[再挑戦•転生•テレポーテーション \]\[何回だって 重ねて逝くんだ \]\[終わりなき愛の随に さあ \]\[愛や厭... \]
提要：打比赛的时候这东西在我脑子里放了四个小时
A.黎明与萤火
容易想到无解的判断：每次删除节点都会至少导致减少 \(4\) 的总度数，且减少的度数总会是 \(4\) 的倍数，因此总度数不为 \(4\) 的倍数的即为无解，搜一遍即可.
随后输出方案数. 考虑到叶节点只能被其父节点删除导致删除，因此可以先从上到下删除叶节点的父节点，再从上到下删除叶节点即可. 实际实现的时候比较简单，两遍搜即可.
复杂度 \(O(N)\)
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>e[200001];
vector<int>son[200001];
int degree[200001];
bool vis[200001];
int fa[200001];
void dfs(int now,int last){
fa[now]=last;
son[last].push_back(now);
for(int i:e[now]){
if(i!=last) dfs(i,now);
}
}
void print1(int now){
if(vis[now]){
for(int i:son[now]) print1(i);
return;
}
for(int i:son[now]){
print1(i);
}
if(degree[now]%2==0){
vis[now]=true;
printf("%d\n",now);
degree[fa[now]]--;
for(int i:son[now]){
degree[i]--;
}
}
}
void print2(int now){
if(vis[now]){
for(int i:son[now]) print2(i);
return;
}
if(degree[now]%2==0){
vis[now]=true;
printf("%d\n",now);
degree[fa[now]]--;
for(int i:son[now]){
degree[i]--;
}
}
for(int i:son[now]){
print2(i);
}
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d",&n);int root=0;
for(int i=1;i<=n;++i){
int x;scanf("%d",&x);
if(x){
e[i].push_back(x);
e[x].push_back(i);
}
}
for(int i=1;i<=n;++i){
if(e[i].size()%2==0){
root=i;
break;
}
}
dfs(root,0);
int res=0;
for(int i=1;i<=n;++i){
res+=son[i].size();
degree[i]=son[i].size()+1;
}
degree[root]--;
if((res+n-1)%4!=0){
cout<<"NO"<<'\n';
return 0;
}
cout<<"YES"<<'\n';
print1(root);
print2(root);
}
B.Darling Dance
这个 Darling Dance 曲绘怎么一股兔子洞味，但是完全不是同一个 P 主
好题
考虑先找出哪些边会在一些节点到 \(1\) 的最短路上，可以发现这些边会构成一颗以 \(1\) 为根的树
证明：在最短路上走环一定不优，因此不存在环，故为树
又因为该树有全部的 \(n\) 个节点，可以推至树上共 \(n-1\) 条边.
因此当 \(k\ge n-1\) 时，直接全选即可.
否则，考虑到不选边缘的边可以使答案更优，直接从根节点搜下来即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;
struct edge{
int to,w,id;
};
vector<edge>e[300001];
int dis[300001];
bool vis[300001];
int pre[300001];
vector<int>e2[300001];
struct node{
int id,dis;
bool operator <(const node &A)const{
return dis>A.dis;
}
};
priority_queue<node>p;
bool istree[300001];
void dij(int s){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s]=0;
p.push({s,dis[s]});
while(!p.empty()){
node u=p.top();
p.pop();
if(vis[u.id]) continue;
istree[pre[u.id]]=true;
vis[u.id]=true;
for(edge i:e[u.id]){
if(!vis[i.to]){
if(dis[i.to]>dis[u.id]+i.w){
dis[i.to]=dis[u.id]+i.w;
p.push({i.to,dis[i.to]});
pre[i.to]=i.id;
}
}
}
}
}
vector<int>ans;
void dfs(int now,int last){
if((int)ans.size()==k) return;
// cout<<"dfs "<<now<<" "<<last<<endl;
for(edge i:e[now]){
if((int)ans.size()==k) return;
if(i.to!=last and istree[i.id]){
ans.push_back(i.id);
dfs(i.to,now);
}
}
}
signed main(){
// freopen("T2.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%lld %lld %lld",&n,&m,&k);
for(int i=1;i<=m;++i){
int x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
e[x].push_back({y,z,i});
e[y].push_back({x,z,i});
}
dij(1);
// for(int i=1;i<=m;++i){
// cout<<i<<" "<<istree[i]<<endl;
// }
dfs(1,0);
cout<<ans.size()<<endl;
for(int i:ans){
cout<<i<<" ";
}
}
C.Non-breath oblige
可以把操作离线下来搞扫描线，但是我不会，所以学了另一种方法
首先可以想到操作能直接用暴力线段树维护
1 操作就相当于两次单点查询于修改
2 操作是区间赋值
3 操作是单点查询
因此可以直接建线段树，但是复杂度太高，考虑优化。
注意到可以直接放弃暴力修改，直接记下操作一改变后的 \(pos\)，然后每次查询直接跳到对应区间查询，这是一种可行的思路，提议转化成询问在 \(l\) 到 \(r\) 之间 \(type_i=3\) 且 \(pos_i\geq l\) 的所有 \(i\) 的 \(val_i\) 之和。
接下来可以上一颗树状数组，维护操作变化，把询问按 \(l\) 降序排序，然后按 \(pos\) 降序依次把 \(val\) 加入树状数组，拿双指针搞，询问的时候直接查 \(query(r)-query(l-1)\) 就行了。
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x){
x=0;bool sym=0;char c=getchar();
while(!isdigit(c)){sym^=(c=='-');c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
if(sym)x=-x;
}
template<size_t N>
inline void read(char (&str)[N]){
size_t n=0;char c=getchar();
while(n<N-1&&!isspace(c)){str[n]=c;c=getchar();++n;}
str[n]=0;
}
template<typename T,size_t N>
inline void read(T (&a)[N],int range=N){
for(int i=1;i<=range;++i){read(a[i]);}
}
template<typename T,typename... Args>
inline void read(T& x,Args&... args){
read(x);read(args...);
}
template<typename T,typename T2>
inline void readarray(T& x,T2& args){
read(x);read(args,x);
}
template<typename func,typename... Args>
inline void readact(int x,function<func>fu,Args&... args){
for(int i=1;i<=x;++i){
read(args...);
fu(args...);
}
}
#define inread(x) int (x);read(x)
inline void write(int A){if(A<0){putchar('-');A=-A;}if(A>9){write(A/10);}putchar(A%10+'0');}
inline void write(long long A){if(A<0){putchar('-');A=-A;}if(A>9){write(A/10);}putchar(A%10+'0');}
inline void write(char A){putchar(A);}
int n,m,Q;
struct tree{
int l,r;
int w;
}t[4000001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
inline void pushdown(int id){
if(t[id].w){
t[tol].w=t[tor].w=t[id].w;
t[id].w=0;
}
}
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r){
t[id].w=0;
return;
}
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
}
void change(int id,int l,int r,int val){
// cout<<id<<" "<<l<<" "<<r<<" "<<t[id].l<<" "<<t[id].r<<" "<<val<<endl;
if(l<=t[id].l and t[id].r<=r){
t[id].w=val;
return;
}
pushdown(id);
if(l<=t[tol].r) change(tol,l,r,val);
if(t[tor].l<=r) change(tor,l,r,val);
}
int ask(int id,int pos){
if(t[id].l==t[id].r or t[id].w) return t[id].w;
int mid(t[id].l,t[id].r);
if(pos<=mid) return ask(tol,pos);
else return ask(tor,pos);
}
long long sum[1000001];
auto lowbit=[](int x){return x&(-x);};
inline void add(int x,int val){
if(!x) return;
while(x<=m){
sum[x]+=val;
x+=lowbit(x);
}
}
inline long long ask(int x){
if(x<1) return 0;
long long ans=0;
while(x){
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
struct area{
int l,r;
};
vector<area>q[1000001];
long long ans[1000001];
struct operation{
int op,x,y,val;
}o[1000001];
int main(){
read(n,m,Q);
build(1,1,n);
bool has2=false;
for(int i=1;i<=m;++i){
read(o[i].op);
if(o[i].op==1){
read(o[i].x,o[i].y);
int hx=ask(1,o[i].x),
hy=ask(1,o[i].y);
change(1,o[i].x,o[i].x,hy);
change(1,o[i].y,o[i].y,hx);
}
else if(o[i].op==2){
has2=true;
read(o[i].x,o[i].y,o[i].val);
change(1,o[i].x,o[i].y,i);
}
else{
read(o[i].x);
o[i].y=ask(1,o[i].x);
}
}
if(!has2){
for(int i=1;i<=Q;++i){
write(0);
putchar('\n');
}
return 0;
}
for(int i=1;i<=Q;++i){
inread(l);inread(r);
q[r].push_back({l,i});
}
// cout<<"?"<<endl;
for(int i=1;i<=m;++i){
// cout<<i<<" "<<m<<endl;
if(o[i].op==3){
add(o[i].y,o[o[i].y].val);
// cout<<i<<" "<<m<<"?"<<endl;
}
for(area j:q[i]){
ans[j.r]=ask(i)-ask(j.l-1);
}
}
// cout<<"?"<<endl;
for(int i=1;i<=Q;++i){
write(ans[i]);
putchar('\n');
}
}