1 条题解

  • 0
    @ 2026-5-7 17:02:37
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    #define x first
    #define y second
    #define pb push_back
    #define mp make_pair
    template <typename T> bool chkmin(T &x,T y){return y<x?x=y,1:0;}
    template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
    template <typename T> void readint(T &x)
    {
    	int f=1;char c;x=0;
    	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
    	x*=f;
    }
    const int MOD=998244353;
    inline int dmy(int x){return x>=MOD?x-MOD:x;}
    inline void inc(int &x,int y){x=dmy(x+y);}
    int qmi(int x,int y)
    {
    	int ans=1;
    	for(;y;y>>=1,x=1ll*x*x%MOD)
    		if(y&1)ans=1ll*ans*x%MOD;
    	return ans;
    }
    const int MAXN=100005,MAXK=18;
    
    int n;
    int a[MAXN];
    map<pii,int> mr;
    vector<int> G[MAXN];
    int dfn[MAXN],dfn_cnt,anc[MAXN][MAXK],dep[MAXN];
    int perm[MAXN],f[MAXN];
    void dfs1(int u)
    {
    	for(int j=1;j<MAXK;++j)anc[u][j]=anc[anc[u][j-1]][j-1];
    	dfn[u]=++dfn_cnt;
    	for(auto v:G[u])
    	{
    		if(v==anc[u][0])continue;
    		anc[v][0]=u;
    		dep[v]=dep[u]+1;
    		dfs1(v);
    	}
    }
    int lca(int u,int v)
    {
    	if(dep[u]>dep[v])swap(u,v);
    	for(int i=MAXK-1;i>=0;--i)if(dep[v]-dep[u]>=(1<<i))v=anc[v][i];
    	if(u==v)return u;
    	for(int i=MAXK-1;i>=0;--i)if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i];
    	return anc[u][0];
    }
    void dfs2(int u)
    {
    	for(auto v:G[u])
    	{
    		if(v==anc[u][0])continue;
    		dfs2(v);
    		f[u]+=f[v];
    	}
    }
    
    int main()
    {
    	#ifdef LOCAL
    	freopen("code.in","r",stdin);
    //	freopen("code.out","w",stdout);
    	#endif
    	readint(n);
    	for(int i=1;i<=n-2;++i)
    	{
    		int t[3];
    		for(int j=0;j<3;++j)readint(t[j]);
    		readint(a[i]);
    		sort(t,t+3);
    		for(int j=0;j<3;++j)
    		{
    			pii p=mp(t[(j+1)%3],t[(j+2)%3]);
    			if(p.x>p.y)swap(p.x,p.y);
    			if(mr.count(p))G[mr[p]].pb(i),G[i].pb(mr[p]);
    			else mr[p]=i;
    		}
    		perm[i]=i;
    	}
    	dfs1(1);
    	sort(perm+1,perm+n-1,[&](int x,int y){return a[x]==a[y]?dfn[x]<dfn[y]:a[x]<a[y];});
    	for(int ii=2;ii<=n-2;++ii)
    	{
    		int x=perm[ii-1],y=perm[ii];
    		if(a[x]==a[y])++f[x],++f[y],f[lca(x,y)]-=2; 
    	}
    	dfs2(1);
    	int res=0;
    	for(int i=2;i<=n-2;++i)
    		if(!f[i])++res;
    	printf("%d\n",res);
    	return 0;
    }
    
    • 1

    信息

    ID
    10550
    时间
    5000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者