列表

详情

NC252105. The Number Of Black Edges

描述

Alice is given a tree with n nodes indexed from 1 to n. Each edge on the tree can be either black or white, and all edges are initially white.

There are three kinds of operations:

1. Change the color of an edge to black.
2. Change the color of an edge to white.
3. Given a node index, count the sum of the number of black edges on the simple path from all odd-indexed nodes to that node.

Note that a simple path is a path between two nodes that does not visit any node more than once.


输入描述

The first line contains two integers n (1 \leq n \leq 100,000) and m (1 \leq m \leq 100,000), separated by a space. Here, n represents the number of nodes on the tree, and m represents the total number of operations.

Next, there are n-1 lines, where the i-th line contains two integers u and v (1 \leq u, v \leq n), representing the two nodes connected by the i-th edge on the tree. Following these are m lines, each representing one operation. The format of each operation is as follows:

- 1 x: Assign the color black to the edge indexed by x.

- 2 x: Assign the color white to the edge indexed by x.

- 3 x: Count the sum of the number of black edges on the simple path from all odd-indexed nodes to the node indexed by x.

输出描述

For each operation 3, output a single integer in a line, indicating the sum of the number of black edges on the simple path from all odd-indexed nodes to the node indexed by x, where x is the parameter of the operation.

示例1

输入: 

5 5
1 2
1 3
1 4
1 5
1 1
3 2
3 3
2 1
3 2

输出: 

3
0
0

示例2

输入: 

11 10
11 2
10 2
1 5
1 4
2 6
4 9
8 5
5 7
2 3
2 1
2 9
2 1
1 1
3 3
1 1
1 8
1 5
2 10
1 8
3 8

输出: 

1
2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 82ms, 内存消耗: 12072K, 提交时间: 2023-05-25 12:00:52 

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
using ll=long long;
using pii=pair<int,int>;
const int N=1e5+5;
vector<int>G[N];
int n,m;
int f[N],l[N],r[N];
int son[N],col[N];
pii e[N];
int tot;
void dfs(int u,int p)
{
    f[u]=p;
    l[u]=++tot;
    if(u&1)son[u]++;
    for(auto v:G[u]){
        if(v!=p){
            dfs(v,u);
            son[u]+=son[v];
        }
    }
    r[u]=tot;
}
ll a[N],tr[N<<2],tag[N<<2];
#define ls ((p)*2)
#define rs ((p)*2+1)
#define mid (((pl)+(pr))/2)
void pushup(int p)
{
    tr[p]=tr[ls]+tr[rs];
}
void addtag(int p,int pl,int pr,ll d)
{
    tag[p]+=d;
    tr[p]+=d*(pr-pl+1);
}
void pushdown(int p,int pl,int pr)
{
    if(tag[p]){
        addtag(ls,pl,mid,tag[p]);
        addtag(rs,mid+1,pr,tag[p]);
        tag[p]=0;
    }
}
void change(int l,int r,ll d,int p=1,int pl=1,int pr=n)
{
    if(l<=pl&&pr<=r){
        addtag(p,pl,pr,d);
        return;
    }
    pushdown(p,pl,pr);
    if(l<=mid)change(l,r,d,ls,pl,mid);
    if(r>mid)change(l,r,d,rs,mid+1,pr);
    pushup(p);
}
ll query(int l,int r,int p=1,int pl=1,int pr=n)
{
    if(l<=pl&&pr<=r)return tr[p];
    pushdown(p,pl,pr);
    ll res=0;
    if(l<=mid)res+=query(l,r,ls,pl,mid);
    if(mid<r)res+=query(l,r,rs,mid+1,pr);
    return res;
}
ll ans;
void update(int x,ll flag)
{
    if(col[x]==flag)return;
    col[x]=flag;
    flag=flag*2-1;
    auto [u,v]=e[x];
    if(f[u]==v)swap(u,v);
    ans+=flag*son[v];
    change(l[v],r[v],flag*(son[1]-son[v]*2));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
        e[i]={u,v};
    }
    dfs(1,1);
    while(m--){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op<=2){
            update(x,2-op);
        }else{
            printf("%lld\n",ans+query(l[x],l[x]));
        }
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 54ms, 内存消耗: 8760K, 提交时间: 2023-05-31 18:11:50 

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<ll,ll> PII;
typedef __int128 ull;
typedef unsigned int ui;
const ll mod=1e9+7;
const int N=1e5+10;

vector<int>g[N];
int n,q;
int dep[N],odd[N],dfn[N],dfn_r[N],idx;
int col[N];
struct node {
	int fa,son;
}e[N];

ll tr[N];

void add(int k,int x){
	for(;k<=n;k+=k&-k)tr[k]+=x;
}
ll ask(int k){
	ll res=0;
	for(;k;k-=k&-k){
		res+=tr[k];
	}
	return res;
}
void modify(int l,int r,int x){
	add(l,x),add(r+1,-x);
}

void dfs(int u,int fa){
	dfn[u]=++idx;
	dep[u]=dep[fa]+1;
	odd[u]=u&1;
	for(auto j:g[u]){
		if(j^fa){
			dfs(j,u);
			odd[u]+=odd[j];
		}
	}
	dfn_r[u]=idx;
}

int main(){
	ios :: sync_with_stdio (false);cin .tie (0);cout .tie (0);
	#ifdef newbie
		freopen("input.in","r",stdin);
		freopen("output.out","w",stdout);
	#endif
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		e[i]={a,b};
		g[a].push_back(b),g[b].push_back(a);
	}
	dfs(1,0);

	for(int i=1;i<n;i++){
		if(dep[e[i].fa]>dep[e[i].son])swap(e[i].fa,e[i].son);
	}

	while(q--){
		int op,x;
		cin>>op>>x;
		if(op==3){
			cout<<ask(dfn[x])<<endl;
		}
		else {
			int d=op==1?1:-1;
			int u=e[x].son;
			if(col[x]==2-op)continue;
			col[x]=2-op;
			int l=dfn[u],r=dfn_r[u];
			modify(1,l-1,d*odd[u]),modify(r+1,n,d*odd[u]);
			modify(l,r,d*(odd[1]-odd[u]));
		}
	}
	return 0;
}

上一题

© 2024 nowcoder.com