Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- using namespace std;
- const int MaxN=500010,inf=1000000000;
- struct edge
- {
- int nod,c;
- };
- vector<edge> v[MaxN];
- int special[MaxN],size[MaxN],niv[MaxN],centru;
- char vaz[MaxN],bun[MaxN];
- void dfs1(int nod,int tata,int &n)
- {
- size[nod]=1;
- n++;
- for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
- if(it->nod!=tata && !vaz[it->nod])
- {
- dfs1(it->nod,nod,n);
- size[nod]+=size[it->nod];
- }
- }
- void get_center(int nod,int tata,int n)
- {
- int ok=1;
- for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
- if(it->nod!=tata && !vaz[it->nod])
- {
- get_center(it->nod,nod,n);
- if(size[it->nod]>n/2+1) ok=0;
- }
- if(n-size[nod]>n/2+1) ok=0;
- if(ok) centru=nod;
- }
- void dfs2(int nod,int tata,int res,int &res1)
- {
- if(res!=inf && niv[nod]!=res) bun[nod]=1;
- if(special[nod]>-1)
- if(res1==inf) res1=special[nod]-niv[nod];
- else if(res1!=special[nod]-niv[nod]) res1=-1;
- for(vector<edge>::iterator it=v[nod].begin();it!=v[nod].end();it++)
- if(it->nod!=tata && !vaz[it->nod])
- {
- niv[it->nod]=niv[nod]+it->c;
- dfs2(it->nod,nod,res,res1);
- }
- }
- void solve(int nod)
- {
- int n=0;
- dfs1(nod,0,n);
- get_center(nod,0,n);
- int center=centru,res=inf;
- if(special[center]>-1) res=special[center];
- for(vector<edge>::iterator it=v[center].begin();it!=v[center].end();it++)
- if(!vaz[it->nod])
- {
- niv[it->nod]=it->c;
- dfs2(it->nod,center,res,res);
- }
- if(res!=inf && res!=0) bun[center]=1;
- res=inf;
- for(vector<edge>::reverse_iterator it=v[center].rbegin();it!=v[center].rend();it++)
- if(!vaz[it->nod])
- {
- niv[it->nod]=it->c;
- dfs2(it->nod,center,res,res);
- }
- vaz[center]=1;
- for(vector<edge>::iterator it=v[center].begin();it!=v[center].end();it++)
- if(!vaz[it->nod])
- solve(it->nod);
- }
- int main()
- {
- //freopen("file.in", "r", stdin);
- //freopen("file.out", "w", stdout);
- int n,k,x,y,s,nr=0;
- scanf("%d%d",&n,&k);
- for(int i=1;i<n;i++)
- {
- scanf("%d%d%d",&x,&y,&s);
- v[x].push_back({y,s});
- v[y].push_back({x,s});
- }
- for(int i=1;i<=n;i++) special[i]=-1;
- for(int i=1;i<=k;i++)
- {
- scanf("%d%d",&x,&s);
- special[x]=s;
- }
- solve(1);
- for(int i=1;i<=n;i++)
- if(!bun[i]) nr++;
- printf("%d\n",nr);
- for(int i=1;i<=n;i++)
- if(!bun[i]) printf("%d ",i);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement